Binary Search, 이진 탐색 알고리즘이란 배열의 원소가 순서대로 sorting이 되어 있다는 가정하에 중간에 있는 element와 찾으려는 element의 크기를 비교해서 찾는 방식입니다.

크기를 비교해서 찾으려는 element보다 중간에 있는 element가 작으면 그 이하를 탐색에서 제외하고, 중간에 있는 element가 그보다 크면 그 이상도 탐색에서 제외합니다. 그래서 찾으려는 값과 중간에 있는 값이 같아질 때까지 반복합니다. 이렇게 하면 탐색 범위를 N/2, N/4 … 이런식으로 절반씩 줄여나갈 수 있다는 장점이 있습니다.

예를 들어, [1,2,4,5,6,7,8,9] 라는 배열에서 6을 찾는다고 가정합니다. 전체 8개로 이루어진 리스트의 중간 element는 약 3번째 index를 가진 5입니다. 그러면 5와 6을 비교했을 때 5보다 6이 크기 때문에 중간 element인 5 이하는 탐색에서 제외합니다. 그래서 6부터 9까지 보는데 여기에서 중간 위치에 있는 element는 7입니다. 7보다 6이 작기 때문에 7 이상부터는 탐색에서 제외합니다. 그러면 이제 6만 남기 때문에 찾는 것이 완료되게 됩니다.

다음은 Python으로 구현한 코드입니다. middle에 있는 값을 구해서 찾으려는 값과 비교하여 같으면 middle에 있는 값의 index를 리턴하고 만약 middle에 있는 값이 찾으려는 x보다 작으면 lower를 현재 middle index 값보다 + 1만큼 증가시켜서 middle 보다 큰 값에서부터 x를 찾습니다. 반대로 middle에 있는 값이 찾으려는 x보다 크면 upper를 현재 middle index 값보다 – 1 만큼 감소시켜서 middle보다 낮은 값에서부터 x를 찾습니다.

def binarySearch(L, x):
    lower = 0
    upper = len(L) - 1
    while lower <= upper:
        middle = (lower + upper) // 2
        if L[middle] == x:
            return middle
        elif L[middle] < x:
            lower = middle + 1
        else:
            upper = middle - 1
    return -1