[Algorithm] 이진탐색(Binary Search)

✨이진탐색(Binary Search)

정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘
처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식

 

 

 

 

 

✨Python 코드 

def binarySearch(array, value, low, high):
	if low > high:
		return False
	mid = (low+high) / 2
	if array[mid] > value:
		return binarySearch(array, value, low, mid-1)
	elif array[mid] < value:
		return binarySearch(array, value, mid+1, high)
	else:
		return mid

 

 

 

 

 

✨Python bisect 라이브러리

import bisect

bisect_left(literable, value) # 왼쪽 인덱스를 구하기
bisect_right(literable, value) # 오른쪽 인덱스를 구하기

 

 

 

 

 

 

 

 

 

 

 

🎈참고자료

https://velog.io/@kimdukbae/%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search