오름차순으로 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘으로, 모든 값을 순회해야하는 일반적인 search보다 더 빠르다. 중앙값을 찾는 값에 비교해서 중앙값이 찾는 값보다 크면 왼쪽을 탐색하고 찾는 값보다 작으면 오른쪽을 탐색한다.
최악의 경우에도 탐색 대상을 절반씩 계속해서 줄여나가기 때문에, 탐색 횟수가 logN이다.
따라서 T(N) = O(logN)
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] > target:
high = mid - 1
if arr[mid] == target:
return mid
if arr[mid] < target:
low = mid + 1
return -1