언제 쓰나
- 정렬된 배열에서 값 찾기, “몇 번째에 있는가”
N이 10만~10억처럼 커서 선형 탐색이 불가능할 때- “조건을 만족하는 최소/최대 값을 구하라” — 답의 범위에 대고 이분 탐색하는 파라메트릭 서치. “최소 시간”, “최대 길이” 같은 최적화 문제가 판별 문제(“시간 T 안에 되는가?“)로 바뀌면 신호다.
핵심 아이디어
중간을 보고, 답이 어느 쪽에 있는지 판단하고, 반대쪽 절반을 통째로 버린다.
key = 7 찾기
[1 3 5 7 9 11 13]
lo mid hi arr[mid]=7 → 발견
key = 9라면:
[1 3 5 7 9 11 13]
↑ 7 < 9 → 왼쪽 절반 버림
[9 11 13]
↑ mid=11 > 9 → 오른쪽 버림
[9] → 발견 7개 → 3번 만에 끝한 번 비교할 때마다 후보가 절반으로 줄어 O(log n)이다. 10억 개라도 30번이면 끝난다. 전제는 하나 — 판단 기준이 단조여야 한다(어느 지점을 경계로 한쪽은 전부 참, 반대쪽은 전부 거짓).
코드 템플릿
기본형 — 정렬된 배열에서 값의 위치 찾기.
def binary_search(arr, key):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] < key:
lo = mid + 1
elif arr[mid] > key:
hi = mid - 1
else:
return mid
return -1파라메트릭 서치 — “조건을 만족하는 최대값” 찾기. 값이 아니라 답의 범위에 이분 탐색을 건다.
def max_ok(lo, hi, ok): # ok(x): x가 조건을 만족하는가
best = lo
while lo <= hi:
mid = (lo + hi) // 2
if ok(mid):
best = mid # 일단 저장하고 더 큰 쪽 시도
lo = mid + 1
else:
hi = mid - 1
return best이미 정렬된 리스트에 값을 넣을 위치만 필요하면 표준 라이브러리 bisect가 빠르고 안전하다.
from bisect import bisect_left, bisect_right
idx = bisect_left(arr, key) # key가 들어갈 가장 왼쪽 위치
count = bisect_right(arr, key) - idx # key의 등장 횟수풀이 과정 따라가기
[1, 3, 5, 7, 9, 11, 13]에서 9를 찾는 과정 — 7개 중 3번 만에 끝난다.
함정
- 경계 갱신 실수로 무한 루프.
lo = mid처럼+1/-1없이 갱신하면 두 칸이 남았을 때 영원히 돈다.lo = mid + 1/hi = mid - 1짝을 지킨다. - 정렬 안 된 배열. 이분 탐색의 전제가 무너지면 조용히 틀린 답이 나온다. 탐색 전에 정렬 여부부터 확인한다.
- 답의 범위 설정. 파라메트릭에서
hi를 너무 작게 잡으면 진짜 답이 범위 밖에 있다. 문제 제약의 최대값으로 넉넉히 잡고 시작한다.