보간 탐색
전화번호부에서 ‘한’ 씨를 찾을 때 가운데부터 펼치지는 않습니다. ‘ㅎ’은 가나다순에서 끝 쪽이니 뒤쪽을 펼칩니다. 보간 탐색은 숫자로 같은 일을 합니다. 목표값의 크기로 그 위치를 추측하며, 고르게 분포한 데이터에서는 그 추측이 놀라울 만큼 정확합니다.
기본 아이디어
이진 탐색은 무엇을 찾든 항상 가운데를 조사합니다. 보간 탐색은 값을 이용합니다. 남은 부분이 10부터 100까지이고 목표값이 70이면, 목표값은 첫 값에서 마지막 값까지의 3분의 2 지점에 있으므로 그 부분의 3분의 2 지점을 조사합니다. 식으로 쓰면 조사 위치는 lo + (target − a[lo]) / (a[hi] − a[lo]) × (hi − lo)입니다. 조사한 뒤에는 이진 탐색과 똑같이 올바른 쪽 부분을 남기고 다시 추정합니다.
두 가지 예
10, 20, 30, 40, 50, 60, 70, 80, 90, 100에서 70을 찾으면 곧바로 7번째 자리를 조사합니다. 조사 1번 만에 찾으며, 이진 탐색은 4번이 필요합니다. 이번에는 1, 2, 3, 4, 5, 6, 7, 8, 9, 999에서 9를 찾아 봅시다. 999 때문에 추정이 매번 앞쪽에 닿아, 1, 2, 3번째 자리처럼 한 자리씩 조사하며 9번 조사해야 합니다. 이진 탐색은 3번이면 됩니다.
얼마나 빠른가
값이 고르게 분포하거나 균등 분포에서 무작위로 뽑혔다면, 조사 한 번마다 남은 부분이 약 n에서 약 √n으로 줄어듭니다. 그래서 평균적으로 약 log₂(log₂ n)번 조사합니다. 값이 10억 개라도 약 5번이며, 이진 탐색은 30번입니다. 값이 매우 고르지 않게 분포하면 조사 한 번에 값 하나만 제외할 수도 있어서, 최악의 경우 선형 탐색만큼 나쁜 n번 조사가 됩니다. 조사할 때마다 나눗셈도 필요하므로, 실제로는 디스크 읽기처럼 조사 비용이 클 때 주로 이득입니다.
역사와 변형
W. W. Peterson이 1957년 임의 접근 저장 장치에서 레코드를 찾기 위해 보간 탐색을 소개했습니다. 키가 고르게 분포할 때 평균 log log n이라는 사실은 1978년 Perl, Itai, Avni가 증명했습니다. 실용적인 변형은 이진 단계를 섞어 나쁜 데이터에 대비합니다. 보간-순차 탐색이나 보간-이진 탐색이 그 예로, 최악의 경우도 log n에 가깝게 유지합니다.
직접 해 보기
앱을 열고 ‘찾을 값’에서 값을 고른 뒤 ‘단계’를 누르세요. 각 조사마다 목표값이 양 끝 값 사이 어디쯤 있고 그것이 몇 번째 자리를 가리키는지 알려 줍니다. ‘분포’를 ‘균등’으로 바꾸면 대부분의 탐색이 조사 한 번에 끝나고, ‘치우침’으로 바꾸면 조사가 목록 앞쪽을 따라 조금씩 나아갑니다. 마지막 타일은 같은 값에 대해 이진 탐색이 몇 단계가 필요한지 보여 줍니다.
자주 묻는 질문
보간 탐색의 시간 복잡도는?
값이 고르게 분포하면 평균 O(log log n), 최악의 경우 O(n)입니다. 추가 메모리는 O(1)이며 정렬된 목록이 필요합니다.
보간 탐색과 이진 탐색의 차이는?
이진 탐색은 항상 남은 부분의 가운데를 조사합니다. 보간 탐색은 양 끝 값으로 판단해 목표값이 있어야 할 곳을 조사합니다. 고르게 분포한 값에서는 훨씬 낫고, 치우친 값에서는 훨씬 나쁠 수 있습니다.
어떤 데이터에 보간 탐색이 알맞나요?
꽤 고르게 분포한 정렬된 숫자 키입니다. 빈 번호가 적은 연속 ID, 규칙적인 이벤트의 타임스탬프, 해시된 키 등이 그렇습니다. 조사 비용은 크고 약간의 계산은 싼 데이터에 알맞습니다.
앱에서 왜 여러 분포를 제공하나요?
분포에 따라 추정의 정확도가 정해지기 때문입니다. 균등한 값에서는 보간 탐색이 거의 마법처럼 보이고, 치우친 값에서는 약점이 드러납니다. 이를 이진 탐색의 횟수와 비교하는 것이 언제 무엇을 쓸지 가장 분명하게 알 수 있는 방법입니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
보간 탐색 해 보기