조사
남은 후보
이진 탐색이라면

  • 목표값
  • 남은 후보
  • 비교 중
  • 제외됨
  • 찾음

보간 탐색 자세히 알아보기

보간 탐색

보간 탐색은 전화번호부를 펼치듯이 정렬된 목록에서 값을 찾습니다. ‘한’ 씨를 찾을 때는 가운데가 아니라 뒤쪽을 펼치죠. 남은 부분의 양 끝 값으로 목표값의 자리를 추정합니다. 찾을 값과 값의 분포를 고르고, 조사를 한 단계씩 진행하며, 추정이 이진 탐색보다 나을 때와 그렇지 않을 때를 확인하세요. ‘재생’을 눌러 탐색을 보거나, ‘단계’와 ‘뒤로’로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 점선은 찾는 값을, 음영 부분은 그 값이 아직 있을 수 있는 범위를 나타냅니다. 보간 탐색은 정렬된 목록이 필요하므로, 정렬되지 않은 목록은 먼저 정렬합니다. 찾을 값, 값의 분포, 막대 개수를 고르거나 직접 숫자를 입력하세요. 보드를 선택한 상태에서는 화살표 키로 한 단계씩 이동하고, 스페이스 바로 재생과 일시 정지를 하며, Home과 End로 처음과 끝으로 이동합니다.

작동 원리

  1. 찾을 값, 값의 분포, 막대 개수를 고르세요. 직접 숫자를 입력해도 됩니다. 보간 탐색이 먼저 정렬합니다.
  2. ‘재생’을 누르거나, ‘단계’와 ‘뒤로’로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 탐색의 원하는 지점으로 이동합니다.
  3. ‘분포’를 ‘균등’, ‘무작위 간격’, ‘치우침’으로 바꿔 가며 ‘조사’와 ‘이진 탐색이라면’을 비교해 보세요.

보간 탐색의 원리

정렬된 목록에서 목표값이 아직 있을 수 있는 부분의 첫 값과 마지막 값을 봅니다. 목표값이 예를 들어 첫 값에서 마지막 값까지의 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를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

편집기로 이동