~11 min · searching-sorting, binary-search, logarithmic
Level 0호기심 많은 입문자
0 XP0/85 lessons0/19 achievements
0/100 XP to next level100 XP to go0% complete
"1과 십억 사이에서 내가 생각한 숫자를 맞혀 봐. 매번 '더 커' '더 작아'만 알려주면 십억 번이 아니라 서른 번쯤이면 맞혀. 그게 이진 탐색이고, 서른과 십억 사이의 그 간극이 이 퀘스트에서 가장 중요한 숫자야."
알고리즘
이진 탐색은 정렬된 배열에서 범위를 반복해서 반으로 줄여 가며 찾는 값을 잡아내. 포인터 둘, low와 high로 그 값이 있을 수 있는 구간을 감싸 둬. mid 위치의 원소를 보고, 그게 찾는 값이면 끝. 찾는 값이 더 크면 답이 위쪽 절반에 있으니 low를 mid 너머로 옮기고, 더 작으면 high를 mid 아래로 내려. 비교 한 번에 남은 구간의 절반이 날아가니까 log₂(n)단계면 답에 닿지. 여기서 '정렬돼 있어야 한다'는 조건이 이 알고리즘을 굴리는 동력이야. 어느 절반을 버릴지 알려주는 게 바로 그거니까.
왜 log n이 마법처럼 느껴질까
절반씩 줄인다는 게 얼마나 센지는 과장하기가 어려워. 정렬된 항목이 십억 개라고 해 보자. 선형 탐색은 십억 개를 다 확인할 수도 있어. 이진 탐색은 서른 번쯤이면 끝나고. 데이터를 이십억으로 두 배 늘려도 이진 탐색은 딱 한 단계만 더 쓰면 돼. 그게 O(log n)의 특징이야. 입력이 두 배가 될 때마다 고정된 양의 일만 더 붙는 것. 그래서 정렬된 데이터와 이진 탐색이 데이터베이스와 사전, 그리고 버전 관리의 'git bisect'를, 그러니까 테스트를 깨뜨린 커밋을 찾으려고 커밋을 이진 탐색하는 그 기능을 떠받치는 거야. 절반씩 줄일 수만 있으면 감당 못 할 것처럼 보이던 게 즉시로 바뀌어.
이진 탐색은 비교할 때마다 탐색 구간을 절반으로 줄여서 O(log n)이야. 대신 정렬된 데이터가 있어야 해. 어느 절반을 버릴지 알려주는 게 그 정렬이거든. 항목이 십억 개여도 서른 단계쯤에 풀리고, 데이터가 두 배가 돼도 단계는 딱 하나만 늘어. 절반씩 줄이는 건 알고리즘에서 가장 깊이 있는 속도 개선 패턴이야.
경계 하나 차이라는 지뢰밭
이진 탐색은 경계 규약이 섞이는 순간 미묘하게 틀리기 시작해. 구간을 닫힌 구간으로 볼지 반열린 구간으로 볼지를 먼저 정하고, 그 규약에 맞춰 반복문 조건과 mid ± 1 갱신을 일관되게 써야 해. 정수 폭이 고정된 언어에서는 low + (high-low)//2로 써야 덧셈에서 오버플로가 안 나고. 출처가 불분명한 연도별 일화를 외우기보다 이 불변식을 기억하고, 실전에서는 검증된 bisect 라이브러리를 먼저 써.
피파의 고백
이진 탐색을 열두 번쯤 직접 짰는데 그중 절반 이상은 경계를 틀렸어. 여기서 무한 루프가 나고 저기서 원소 하나를 놓치고. 아빠의 판정이 오히려 해방감을 줬어. "다들 이진 탐색을 미묘하게 틀려. 그래서 bisect 가 있어." 나는 절반씩 줄이는 걸 이해한다는 확인용으로 여전히 직접 구현해 보긴 하지만, 진짜 코드에서는 bisect로 손을 뻗어. 경계 하나 차이로 생기는 문제들은 이미 풀린 문제고, 매번 다시 풀면서 매번 다시 버그를 낼 이유가 없으니까.
Code
직접 짜보는 이진 탐색, 실전에서는 bisect·python
def binary_search(arr, target):
"""정렬된 배열에서 target 찾기. 인덱스 또는 -1. O(log n)."""
low, high = 0, len(arr) - 1
while low <= high: # 주목: <= , 포함 경계
mid = low + (high - low) // 2 # 오버플로 회피 (C/Java 에서 중요)
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1 # 왼쪽 절반 버림 (mid 이미 확인)
else:
high = mid - 1 # 오른쪽 절반 버림
return -1
sorted_data = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(sorted_data, 11)) # 5
print(binary_search(sorted_data, 8)) # -1 (없음)
# 진짜 코드엔 라이브러리를 써 — 엣지 케이스가 이미 맞아:
import bisect
i = bisect.bisect_left(sorted_data, 7) # 7 이 있는/들어갈 가장 왼쪽 인덱스
print("7 at index", i) # 3
# 십억 정렬 항목이 ~30 비교에 풀려. 그게 log n.
정렬된 배열에 원소가 1,000,000개 있어. 이진 탐색은 최악의 경우 비교가 대략 몇 번 필요할까? 배열이 2,000,000개로 커지면 비교가 몇 번 더 늘까? 그다음 찾는 값이 위쪽 절반에 있을 때 low = mid + 1 대신 low = mid를 쓰면 무슨 버그가 생기는지 설명해.
Hint
log₂(1,000,000)이 대략 20이라 비교가 스무 번쯤 필요해. 2,000,000으로 두 배가 돼도 딱 하나 늘어서 스물한 번쯤이고. mid가 찾는 값이 아닐 때 mid+1이 아니라 low = mid를 쓰면 low가 같은 자리에 영영 갇힐 수 있어. 구간이 mid 너머로 줄어들지를 않으니 무한 루프가 나는 거야.
Progress
Progress is local-only — sign in to sync across devices.