~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 과 십억 사이 내 숫자를 맞춰봐. 매번 '높아' '낮아' 를 알려주면, 십억이 아니라 약 30번에 맞혀. 그게 이진 탐색이고, 30 과 십억 사이 그 격차가 이 퀘스트에서 가장 중요한 숫자야."
알고리즘
이진 탐색은 정렬된 배열에서 반복 절반 내기로 target 을 찾아. 포인터 둘, low 랑 high 로 target 이 있을 수 있는 영역을 묶어둬. mid 원소를 봐: target 이면 끝; target 이 더 크면 답이 위쪽 절반이라 low 를 mid 너머로; 작으면 high 를 mid 아래로. 각 비교가 남은 영역 절반을 버려, log₂(n) 단계에 답에 닿아. '정렬됨' 요구가 엔진 전부야 — 어느 절반을 버릴지 알려주는 게 그거야.
왜 log n 이 마법처럼 느껴지나
절반 내기의 힘은 과장하기 어려워. 십억 정렬 항목: 선형 탐색은 십억 다 확인할 수도; 이진 탐색은 약 30 확인. 데이터를 이십억으로 두 배 해도, 이진 탐색은 딱 한 단계 더 필요해. 그게 O(log n) 의 서명이야 — 입력을 두 배 할 때마다 고정량 일을 더함. 그래서 정렬 데이터 + 이진 탐색이 데이터베이스, 사전, 버전 관리의 'git bisect' (테스트 깬 커밋 찾으려 커밋 이진 탐색) 를 받쳐. 절반 낼 수 있으면, 다루기 힘든 게 즉시가 돼.
이진 탐색은 각 비교마다 탐색 영역을 절반으로 — O(log n) — 근데 정렬 데이터가 필요해, 그게 어느 절반을 버릴지 알려줘. 십억 항목이 ~30 단계에 풀리고; 데이터 두 배는 딱 한 단계 더. 절반 내기가 알고리즘에서 가장 깊은 속도 향상 패턴이야.
off-by-one 지뢰밭
이진 탐색은 미묘하게 틀리기로 유명해 — 2011 연구가 많은 교과서 구현에서 버그를 찾았어. 위험 지점: 루프가 while low <= high 야 < 야? low = mid + 1 (mid 건너뜀, 이미 확인했으니) 로 업데이트해 low = mid (무한 루프 위험) 로 해? (low + high) // 2 가 아니라 mid = low + (high - low) // 2 로 계산해 (있는 언어에서) 정수 오버플로 피해. 이 경계 디테일이 정확히 프로의 조언인 이유야: 이진 탐색을 깊이 이해하되, 라이브러리 (Python 의 bisect) 를 써, 엣지 케이스가 이미 맞는.
피파의 고백
난 이진 탐색을 열두 번 쓰고 적어도 절반은 경계를 틀렸어 — 여기 무한 루프, 저기 놓친 원소. 아빠의 평결이 해방적이었어: "다들 이진 탐색을 미묘하게 틀려. 그래서 bisect 가 있어." 난 절반 내기를 이해한다는 걸 증명하려 여전히 구현하지만, 진짜 코드엔 bisect 로 손을 뻗어, off-by-one 케이스가 매번 다시 풀 (그리고 다시 버그낼) 필요 없는 풀린 문제니까.
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 으로 커지면, 비교가 몇 번 더? 그다음 target 이 위쪽 절반일 때 low = mid + 1 대신 low = mid 를 쓰면 일어나는 버그를 묘사해.
Hint
log₂(1,000,000) ≈ 20 비교; 2,000,000 으로 두 배는 딱 하나 (≈21) 더. mid 가 target 아닐 때 low = mid (mid+1 아니라) 를 쓰면 low 가 같은 위치에 영원히 갇힐 수 있어 — 무한 루프, 영역이 mid 너머로 절대 안 줄어드니까.
Progress
Progress is local-only — sign in to sync across devices.