[Python] 이분/이진 탐색 (Binary Search)

이분 탐색 또는 이진 탐색은 찾고자 하는 수를 두 부분으로 나눠서 찾는 기법입니다. 따라서 순차 탐색(linear search) 보단 더 빠른 성능을 보입니다. 이분 탐색을 하기 위해선 주어진 탐색 리스트가 이미 정렬이 되어 있다는 전제가 깔려야 합니다.

아래는 이진 탐색의 탐색 순서입니다.

1. 탐색 리스트가 정렬이 되어 있지 않다면 정렬
2. left, right, mid를 잡아줌 (리스트 첫 번째는 left, 리스트 마지막은 right, 리스트의 중간 값은 mid
   1. 여기서 값보단 리스트의 인덱스로 잡는 것이 더 범용적으로 사용할 수 있음
3. mid 값과 찾고자 하는 값 비교
4. mid값이 더 크면 right 값을 mid -1, mid값이 더 작으면 left값을 mid + 1로 세팅
5. left > right가 될 때까지 2~4번 반복

이와 같이 진행하면 탐색 사이즈가 계속 1/2씩 줄어들기 때문에 시간복잡도가 O(logN)이 나오게 됩니다.

아래는 위 탐색 순서를 표현한 코드입니다.

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

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

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
result_index = binary_search(arr, 6)
print(result_index, arr[result_index])
# 5 6

만약 해당 탐색이 끝날 떄까지 반환이 되지 않았다면 주어진 리스트에 조건이 없다는 의미입니다.

추가로 해당 이진 탐색을 봤을 때, 이진 탐색 트리 (Binary Search Tree, BST)와 다른게 뭘까 하고 급 헷갈렸는데 명확하게 다른 개념입니다. BST는 트리 구조로 만든 다음, 찾아가는 방식입니다.