이진 탐색은 코딩 테스트용 기법에 그치지 않고 데이터베이스, 버전 관리, 네트워크, 부하 분산 같은 실제 시스템 곳곳에 들어 있습니다. 이 장에서는 탐색이 쓰이는 대표적인 자리와 실무에서 자주 겪는 함정을 정리합니다.
시스템 속의 탐색
- 데이터베이스 색인: B-트리 색인은 한 노드(페이지) 안에 정렬된 키를 담고, 노드 안에서는 이진 탐색으로 다음에 내려갈 자식을 고릅니다.
WHERE price BETWEEN 100 AND 200 같은 범위 질의가 빠른 이유가 정렬 순서 덕분입니다. - LSM 트리 저장소: RocksDB 같은 저장소는 정렬된 파일(SSTable)마다 블록 색인을 두고 이진 탐색으로 블록을 찾습니다. 없는 키를 찾는 비용을 줄이려고 앞에 블룸 필터를 둡니다.
- 표준 라이브러리: Python
bisect, C++ std::lower_bound·std::equal_range, Java Arrays.binarySearch·Collections.binarySearch, Rust slice::binary_search·partition_point가 모두 같은 원리입니다. - 버전 관리:
git bisect는 "좋은 커밋"과 "나쁜 커밋" 사이 이력을 이진 탐색해 버그를 들여온 커밋을 찾습니다. - 가중치 무작위 선택과 분포: 누적 합 배열에서 난수의 위치를 이진 탐색하면 가중치에 비례해 항목을 고를 수 있습니다. Python
random.choices도 내부에서 bisect를 씁니다.
git bisect로 회귀 버그 찾기
커밋이 1,000개 쌓여 있어도 약 10번 확인하면 문제를 처음 일으킨 커밋을 찾을 수 있습니다. 확인을 스크립트로 자동화할 수도 있습니다.
git bisect start
git bisect bad # 지금 커밋은 문제가 있음
git bisect good v1.4.0 # 이 태그는 정상이었음
# Git이 꺼내 준 커밋을 확인하고 표시하기를 반복
git bisect good # 또는 git bisect bad
# 테스트 명령으로 자동화: 종료 코드 0이면 good, 125를 뺀 1~127이면 bad
git bisect run python -m pytest tests/test_parser.py -x -q
git bisect reset
IP 주소 범위 찾기
겹치지 않는 주소 범위 목록에서 어떤 IP가 어느 범위에 드는지 찾는 일은 "시작 주소가 IP 이하인 마지막 범위"를 구하는 문제입니다. 범위가 수십만 개여도 조회 한 번이 O(log n)입니다.
from bisect import bisect_right
from ipaddress import ip_address
ranges = [ # (시작, 끝, 이름) — 시작 주소 순으로 정렬, 겹치지 않음
(int(ip_address("10.0.0.0")), int(ip_address("10.255.255.255")), "internal"),
(int(ip_address("192.168.0.0")), int(ip_address("192.168.255.255")), "lab"),
(int(ip_address("203.0.113.0")), int(ip_address("203.0.113.255")), "docs"),
]
starts = [start for start, _, _ in ranges]
def lookup(ip):
n = int(ip_address(ip))
i = bisect_right(starts, n) - 1
if i >= 0 and n <= ranges[i][1]:
return ranges[i][2]
return None
print(lookup("10.1.2.3"), lookup("192.168.5.5"), lookup("8.8.8.8"))
# internal lab None
가중치에 따라 서버 고르기
import random
from bisect import bisect_right
from itertools import accumulate
servers = ["a", "b", "c"]
cumulative = list(accumulate([5, 3, 2])) # [5, 8, 10]
def pick():
r = random.random() * cumulative[-1] # 0 이상 10 미만
return servers[bisect_right(cumulative, r)]
counts = {s: 0 for s in servers}
for _ in range(10_000):
counts[pick()] += 1
print(counts) # 대략 a 5000, b 3000, c 2000
r이 0 이상 5 미만이면 a, 5 이상 8 미만이면 b, 나머지는 c가 뽑힙니다. 경계값 5에서 b가 나와야 하므로 bisect_left가 아니라 bisect_right를 씁니다.
자주 겪는 함정
- 정렬되지 않은 입력: 이진 탐색은 오류 없이 엉뚱한 답을 돌려줍니다. 입력이 정렬되어 있다는 가정을 검사하거나 문서로 남깁니다.
- 정렬 기준 불일치: 대소문자 무시, 로캘 순서, 사용자 정의 키로 정렬했다면 탐색도 같은 기준으로 비교해야 합니다. Python 3.10부터는
bisect에 key를 줄 수 있습니다. - off-by-one과 무한 반복: 닫힌 구간과 반열린 구간을 섞지 말고,
lo = mid처럼 구간이 줄지 않는 갱신을 피합니다. - 정수 오버플로: 고정 크기 정수 언어에서는
lo + (hi - lo) / 2를 씁니다. - 실수 비교: 실수 범위 탐색은
lo < hi 대신 고정 반복 횟수나 허용 오차로 끝냅니다. - 반복문 안의 선형 탐색: 반복문 안에서
x in some_list를 쓰면 전체가 O(n^2)이 됩니다. 정확한 일치만 필요하면 set으로 바꿉니다.
정리
- B-트리 색인, SSTable, 표준 라이브러리,
git bisect, 가중치 선택 모두 정렬된 순서 위의 이진 탐색입니다. - 범위 조회와 "직전 값" 찾기는
bisect_right(...) - 1 꼴로 자주 나타납니다. - 정렬 가정, 비교 기준, 구간 꼴, 오버플로, 실수 종료 조건을 점검하면 대부분의 탐색 버그를 막을 수 있습니다.
더 읽을거리
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.