검색 5종 경주 — 선형 · 이진 · 점프 · 지수 · 보간
같은 정렬·균등 분포 배열(64개)에서 뒤쪽 값을 다섯 방식이 찾는 비교 횟수를 실측해 레인 경주로 대비시킨다.
1 / 10정렬·균등 분포 배열 64개에서 뒤쪽(60번)의 값을 다섯 방식이 찾습니다. 진행 = 비교 횟수 실측.
선형O(n)탐색 중
이진O(log n)탐색 중
점프O(√n)탐색 중
지수O(log i)탐색 중
보간O(log log n)탐색 중
각 레인의 속도 = 비교 횟수의 역수 (실측)
단계 목록 · 키보드 ←/→ 이동, Space 재생
다섯 검색의 순위는 '전제의 값'이다 — 전제 없음(선형) < 정렬(이진·지수) < 정렬+순차 매체(점프) < 정렬+균등 분포(보간). 전제가 깨지면 순위도 무너진다.
왜 헷갈리는가
"보간 탐색이 O(log log n)이면 이진 탐색은 왜 쓰나?" — 보간의 속도는 균등 분포라는 전제를 산 것이고, 치우친 분포에서는 O(n)으로 무너진다. 기본기가 이진 탐색인 이유: 전제가 '정렬' 하나뿐이라 배신당할 일이 적다.
다섯 방식의 성격
같은 질문(어디 있나)에 다른 정보를 쓴다.
- 선형: 아무 전제 없음 — 하나씩 다 본다. 작은 배열, 비정렬, 한 번만 찾을 때는 이게 답이다(정렬 비용이 더 비싸므로).
- 이진: '정렬' 전제 — 가운데와 비교해 절반을 버린다. 64억 개도 33번. 만능 기본기.
- 점프: '정렬 + 뒤로 가기 비싼 매체' — √n 보폭으로 건너뛰고 블록 안을 선형으로. 테이프·순차 저장 시절의 지혜.
- 지수: '크기를 모르거나 목표가 앞쪽' — 범위를 1,2,4,8…로 넓혀 잡고 이진. 무한 스트림·언바운드 배열용.
- 보간: '정렬 + 균등 분포' — 전화번호부에서 '박'씨를 중간이 아니라 앞쪽 1/4부터 펴 보는 사람의 직관. O(log log n).
현업의 모습
DB 인덱스(B-트리)는 이진 탐색의 디스크 버전이고, git bisect는 커밋 이력의 이진 탐색이며, 시계열 스토리지가 시간 범위를 좁히는 것은 지수+이진의 조합이다. '균등 분포 전제'가 보장되는 드문 곳(해시된 키 공간)에서만 보간류가 등장한다.
기억할 것
- 속도 순위 = 전제의 개수. 공짜 속도는 없다.
- 기본기는 이진 탐색 — 전제가 '정렬' 하나뿐이다.
- 보간의 O(log log n)은 균등 분포가 깨지면 O(n)으로 추락한다.
- 한 번만 찾을 거면 선형이 이긴다 — 정렬 비용 O(n log n)을 잊지 말 것.