이진 탐색 — 정렬된 데이터의 고속 검색

이 토픽을 마치면

이진 탐색의 원리를 이해하고, O(log n)이 왜 빠른지 체감하며, 직접 구현할 때의 주의점을 알게 됩니다.

사전에서 단어 찾기

종이 사전에서 "Python"을 찾는다고 합시다. 첫 페이지부터 한 장씩 넘기지 않습니다. 가운데를 펴서 "M"이면 뒤쪽으로, "S"면 앞쪽으로 다시 가운데를 펍니다.

이것이 이진 탐색입니다. 한 번 볼 때마다 찾아야 할 범위가 절반으로 줄어듭니다.

순차 탐색 vs 이진 탐색

정렬된 1～100에서 73을 찾는다고 합시다.

순차 탐색 — 1, 2, 3, ..., 73. 73번 비교해야 합니다.

이진 탐색:

[1 ............... 50 ............... 100]  → 50 < 73 → 오른쪽
[51 ......... 75 ......... 100]             → 75 > 73 → 왼쪽
[51 .... 63 .... 74]                        → 63 < 73 → 오른쪽
[64 .. 69 .. 74]                            → 69 < 73 → 오른쪽
[70 . 72 . 74]                              → 72 < 73 → 오른쪽
[73]                                        → 찾았다!

6번 만에 찾았습니다. 100개에서 73번 vs 6번 — 벌써 12배 차이입니다.

O(log n)의 위력

10억 개의 데이터에서 30번만 비교하면 답을 찾습니다. 매번 반으로 쪼개니까 2^30 ≈ 10억이기 때문입니다.

구현

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid          # 찾음
        elif arr[mid] < target:
            left = mid + 1      # 오른쪽 절반
        else:
            right = mid - 1     # 왼쪽 절반

    return -1                   # 없음

numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(numbers, 23))  # 5 (인덱스)
print(binary_search(numbers, 10))  # -1 (없음)

주의점 3가지

1. 정렬이 전제조건

이진 탐색은 정렬된 데이터에서만 작동합니다. 정렬이 안 되어 있으면 가운데 값과 비교해봐야 왼쪽/오른쪽을 결정할 수 없습니다.

정렬 비용은 O(n log n)입니다. 한 번만 찾을 거라면 순차 탐색 O(n)이 더 빠릅니다. 이진 탐색이 유리한 건 정렬해놓고 여러 번 검색할 때입니다.

2. left <= right (등호)

while left <= right에서 <=가 아니라 <로 쓰면 요소가 1개 남았을 때 검사를 건너뜁니다. 맞는 값이 마지막 하나인 경우 못 찾습니다.

3. mid 계산의 오버플로우

# 안전한 계산
mid = left + (right - left) // 2

(left + right) // 2는 Python에서는 문제없지만, C/Java처럼 정수 크기가 고정된 언어에서는 left + right가 오버플로우할 수 있습니다. 습관적으로 위 방식을 쓰는 게 안전합니다.

Python 내장 — bisect

import bisect

numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

# 삽입 위치 찾기
idx = bisect.bisect_left(numbers, 23)
print(idx)  # 5

# 값이 있는지 확인
if idx < len(numbers) and numbers[idx] == 23:
    print("찾음")

bisect 모듈은 이진 탐색을 C로 구현해놓은 것입니다. 직접 구현보다 빠르고, "정렬된 리스트에 값을 삽입할 위치"를 찾는 데도 쓸 수 있습니다.

핵심

이진 탐색은 정렬된 데이터에서 매번 절반을 버리는 알고리즘입니다. 시간 복잡도 O(log n) — 10억 개에서 30번이면 찾습니다. 전제 조건은 정렬 — 한 번 정렬 후 여러 번 검색할 때 효과적입니다.