- 목표값
- 남은 후보
- 비교 중
- 제외됨
- 찾음
보간 탐색
보간 탐색은 전화번호부를 펼치듯이 정렬된 목록에서 값을 찾습니다. ‘한’ 씨를 찾을 때는 가운데가 아니라 뒤쪽을 펼치죠. 남은 부분의 양 끝 값으로 목표값의 자리를 추정합니다. 찾을 값과 값의 분포를 고르고, 조사를 한 단계씩 진행하며, 추정이 이진 탐색보다 나을 때와 그렇지 않을 때를 확인하세요. ‘재생’을 눌러 탐색을 보거나, ‘단계’와 ‘뒤로’로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 점선은 찾는 값을, 음영 부분은 그 값이 아직 있을 수 있는 범위를 나타냅니다. 보간 탐색은 정렬된 목록이 필요하므로, 정렬되지 않은 목록은 먼저 정렬합니다. 찾을 값, 값의 분포, 막대 개수를 고르거나 직접 숫자를 입력하세요. 보드를 선택한 상태에서는 화살표 키로 한 단계씩 이동하고, 스페이스 바로 재생과 일시 정지를 하며, Home과 End로 처음과 끝으로 이동합니다.
작동 원리
- 찾을 값, 값의 분포, 막대 개수를 고르세요. 직접 숫자를 입력해도 됩니다. 보간 탐색이 먼저 정렬합니다.
- ‘재생’을 누르거나, ‘단계’와 ‘뒤로’로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 탐색의 원하는 지점으로 이동합니다.
- ‘분포’를 ‘균등’, ‘무작위 간격’, ‘치우침’으로 바꿔 가며 ‘조사’와 ‘이진 탐색이라면’을 비교해 보세요.
보간 탐색의 원리
정렬된 목록에서 목표값이 아직 있을 수 있는 부분의 첫 값과 마지막 값을 봅니다. 목표값이 예를 들어 첫 값에서 마지막 값까지의 40% 지점에 있다면, 그 부분의 40% 지점에 있는 자리를 조사합니다. 그 자리의 값이 목표값이면 끝입니다. 더 작으면 그 뒤의 자리만 남고, 더 크면 그 앞의 자리만 남습니다. 남은 부분에서 다시 추정합니다. 목표값이 첫 값보다 작거나 마지막 값보다 크면 목록에 없습니다.
추정이 잘 맞을 때
10, 20, 30처럼 값이 고르게 분포하면 첫 추정이 목표값이나 아주 가까운 곳에 닿고, 평균적으로 약 log₂(log₂ n)번 조사하면 됩니다. 값이 10억 개라도 약 5번이면 되며, 이진 탐색은 30번입니다. 1, 2, 3, 4, 1000처럼 값이 몰려 있으면 추정이 계속 엉뚱한 곳에 닿고 조사 한 번에 값 하나만 제외할 수도 있어서, 최악의 경우 n번 조사합니다. 이진 탐색은 약 log₂ n번보다 나빠지지 않습니다.
자주 묻는 질문
보간 탐색은 어떻게 동작하나요?
정렬된 목록에서 남은 부분의 첫 값과 마지막 값으로 목표값이 있어야 할 위치를 추정하고, 그 자리를 조사한 뒤, 올바른 쪽 부분만 남깁니다. 가운데보다 더 똑똑하게 추측하는 이진 탐색이라고 할 수 있습니다.
보간 탐색이 이진 탐색보다 빠른가요?
값이 고르게 분포하면 그렇습니다. 평균적으로 약 log₂ n번 대신 약 log₂(log₂ n)번 조사합니다. 값이 고르지 않게 분포하면 훨씬 느릴 수 있어 최대 n번 조사하지만, 이진 탐색은 약 log₂ n번을 넘지 않습니다.
왜 느려질 수 있나요?
추정이 값이 고르게 커진다고 가정하기 때문입니다. 대부분의 값이 작고 몇 개만 아주 크면, 작은 목표값에 대한 추정이 계속 앞쪽에 닿아 매번 값을 한두 개만 제외합니다.
보간 탐색은 어디에 쓰이나요?
키가 거의 고르게 분포하고 조사 비용이 큰 곳입니다. 예를 들어 디스크에서 숫자 ID나 해시로 레코드를 찾을 때입니다. 많은 시스템이 이진 탐색과 함께 써서 최악의 경우에도 성능을 지킵니다.
제 숫자가 어딘가로 전송되나요?
아니요. 탐색은 브라우저에서 실행되며, 마지막 설정은 이 브라우저의 로컬 저장소에 남습니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
편집기로 이동