반 씩 가르며 탐색해 나가서 시간복잡도 logN이다.
정렬된 리스트에만 사용 가능하다. (재사용할 일이 많을 때 순차탐색보다 빠르다)

기본

정렬된 리스트와 찾을 값을 넣어주면 그 값의 index를 반환 해준다.

def binary_search(arr, value):
    first, last = 0, len(arr)-1

    while first <= last:
        mid = (first + last) // 2
        if arr[mid] == value:
            return mid
        if arr[mid] > value:
            last = mid - 1
        else:
            first = mid + 1

응용

기본 알고리즘은 중복값을 가지고 있거나 그 값이 없을 경우 사용이 어렵다.
아래 응용 알고리즘은 중복값이 있을 시 가장 왼쪽의 index를 반환해주고 그 값이 없을 경우 삽입될 index를 반환해준다.

def binary_search(arr, value):
    first, last = 0, len(arr)
    while first < last:
        mid = (first + last) // 2
        if arr[mid] >= value:
            last=mid
        else:
            first = mid + 1
     return first