이진 탐색 알고리즘 원리, 코드, 시간 복잡도

이진 탐색이 해결하는 문제

선형 탐색은 항목을 하나씩 확인하므로 최대 n번 비교해야 합니다. 데이터가 정렬되어 있으면 훨씬 잘할 수 있습니다. 목표 값을 가운데 항목과 비교하면 어느 절반을 남길지 바로 알 수 있습니다. 종이 사전에서 단어를 찾는 방법과 같은 발상입니다.

이진 탐색은 배열뿐 아니라 단조로운 것이라면 무엇에든 적용됩니다. 어떤 참/거짓 조건이 작은 값에서는 모두 거짓이고 큰 값에서는 모두 참이라면, 이진 탐색으로 그 경계를 찾을 수 있습니다. 이를 정답에 대한 이진 탐색(binary search on the answer)이라고 합니다.

단계별 예제

정렬된 리스트 [2, 5, 8, 12, 16, 23, 38, 56, 72, 91](인덱스 0~9)에서 23을 찾아 봅시다. 아직 확인해야 할 범위를 나타내는 인덱스 lo와 hi 두 개를 유지합니다.

선형 탐색은 6번 비교하지만 여기서는 3번이면 됩니다. 항목이 100만 개인 리스트라도 이진 탐색은 최대 20번이면 됩니다.

파이썬 구현

아래 반복문 버전은 닫힌 범위 [lo, hi]를 사용합니다. 양 끝이 모두 아직 후보입니다. 범위가 비어 있지 않은 동안 반복합니다.

def binary_search(items, target):
    lo, hi = 0, len(items) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            lo = mid + 1          # target is in the right half
        else:
            hi = mid - 1          # target is in the left half
    return -1                     # not found
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(data, 23))   # 5
print(binary_search(data, 7))    # -1

실제 파이썬 코드에서는 표준 라이브러리 모듈 bisect를 사용하세요. bisect_left는 리스트를 정렬된 상태로 유지하면서 목표 값을 넣을 수 있는 가장 왼쪽 위치를 반환하므로, 값이 있는지도 알 수 있습니다.

from bisect import bisect_left, bisect_right, insort
data = [1, 3, 3, 3, 7, 9]
i = bisect_left(data, 3)
print(i, bisect_right(data, 3))   # 1 4  (3 occupies indexes 1..3)
print(i < len(data) and data[i] == 3)   # True: 3 is present
print(bisect_left(data, 5))       # 4: insertion point for 5
insort(data, 5)
print(data)                       # [1, 3, 3, 3, 5, 7, 9]

시간 복잡도와 공간 복잡도

변형 문제: 첫 번째, 마지막, 정답에 대한 이진 탐색

많은 문제는 값이 있는지가 아니라 경계가 어디인지를 묻습니다. x 이상인 첫 인덱스, x의 마지막 등장 위치, 조건을 만족하는 가장 작은 수 같은 것입니다. 이럴 때는 반열린 범위 [lo, hi)를 쓰고 중간에 끝내지 마세요.

def first_true(lo, hi, ok):
    """Smallest x in [lo, hi) with ok(x) True, or hi if none.
    ok must be False...False True...True over the range."""
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid          # mid may be the answer, keep it
        else:
            lo = mid + 1      # mid is too small
    return lo
data = [1, 3, 3, 3, 7, 9]
print(first_true(0, len(data), lambda i: data[i] >= 3))   # 1
# Integer square root of 200: largest x with x*x <= 200
print(first_true(0, 201, lambda x: x * x > 200) - 1)      # 14

• 하한(x 이상인 첫 인덱스): bisect_left.
• 상한(x 초과인 첫 인덱스): bisect_right.
• 정렬된 리스트에서 x의 개수: bisect_right(a, x) - bisect_left(a, x).
• 회전된 정렬 배열에서 탐색, 피크 찾기, 최댓값의 최소화(예: D일 안에 모든 짐을 배송할 수 있는 가장 작은 용량)는 대표적인 면접 변형 문제입니다.

흔한 실수

• 범위 규칙을 섞어 쓰는 경우입니다. 닫힌 범위에서는 lo <= hi와 hi = mid - 1을, 반열린 범위에서는 lo < hi와 hi = mid를 씁니다. 섞으면 무한 루프가 생기거나 요소를 건너뜁니다.
• lo = mid + 1 대신 lo = mid라고 쓰는 경우입니다. hi = lo + 1일 때 mid가 lo와 같아져서 반복이 끝나지 않습니다.
• 정렬되지 않은 데이터에 이진 탐색을 쓰는 경우입니다. 오류 없이 잘못된 답을 반환합니다.
• Java, C, C++처럼 정수 크기가 고정된 언어에서 (lo + hi) / 2가 오버플로하는 경우입니다. lo + (hi - lo) / 2를 쓰세요. 파이썬 정수는 오버플로하지 않으므로 (lo + hi) // 2도 안전합니다.
• 중복된 값 중 첫 번째 등장 위치를 찾아야 하는데 처음 찾은 일치 항목을 반환하는 경우입니다.

이진 탐색을 쓰기 좋은 때

실제 활용 사례로는 데이터베이스와 파일 시스템 인덱스(B-트리가 이 발상을 일반화한 것), 버그를 일으킨 커밋을 찾는 git bisect, IP 대역 같은 범위 표에서 값 찾기, 임곗값을 찾는 여러 수치 문제가 있습니다.