비교
남은 후보
이진 탐색이라면

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

지수 탐색 자세히 알아보기

지수 탐색

지수 탐색은 정렬된 목록에서 두 단계로 값을 찾습니다. 먼저 1, 2, 4, 8, 16번째 자리처럼 매번 두 배로 늘려 가며 확인하다가, 그 값이 목표값보다 작지 않으면 멈춥니다. 그다음 마지막 두 자리 사이의 범위를 이진 탐색합니다. 찾을 값을 고르고, 앞쪽에 있는 목표값을 왜 몇 번의 비교만으로 찾는지 확인해 보세요. ‘재생’을 눌러 탐색을 보거나, ‘단계’와 ‘뒤로’로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 점선은 찾는 값을, 음영 부분은 그 값이 아직 있을 수 있는 범위를 나타냅니다. 지수 탐색은 정렬된 목록이 필요하므로, 정렬되지 않은 목록은 먼저 정렬합니다. 찾을 값과 막대 개수를 고르거나 직접 숫자를 입력하세요. 보드를 선택한 상태에서는 화살표 키로 한 단계씩 이동하고, 스페이스 바로 재생과 일시 정지를 하며, Home과 End로 처음과 끝으로 이동합니다.

작동 원리

  1. 찾을 값과 막대 개수를 고르세요. 직접 숫자를 입력해도 됩니다. 지수 탐색이 먼저 정렬합니다.
  2. ‘재생’을 누르거나, ‘단계’와 ‘뒤로’로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 탐색의 원하는 지점으로 이동합니다.
  3. 앞쪽에 있는 값과 끝쪽에 있는 값을 각각 찾아보고, 비교 횟수를 ‘이진 탐색이라면’과 비교해 보세요.

지수 탐색의 원리

1번째 자리의 값을 봅니다. 목표값보다 작으면 2번째, 그다음 4, 8, 16번째 자리처럼 매번 두 배로 늘려 가며 봅니다. 작지 않은 값이 나오면 바로 멈춥니다. 목표값은 직전에 본 자리 뒤, 그리고 이 자리 앞에만 있을 수 있습니다. 그 범위를 이진 탐색합니다. 두 배로 늘리다 목록 끝을 넘어가면, 마지막으로 본 자리부터 끝까지를 이진 탐색합니다.

앞쪽에서 빠르고, 길이도 필요 없다

i번째 자리의 목표값까지 가는 데 두 배로 늘리는 단계는 약 log₂ i번 보고, 찾아낸 범위에는 값이 i개보다 적으므로 이진 탐색이 약 log₂ i번 더 듭니다. 모두 합쳐 약 2 log₂ i번이며, 이는 목록의 길이가 아니라 목표값의 위치에 달려 있습니다. 앞쪽의 목표값은 일반 이진 탐색보다 빨리 찾고, 끝쪽의 목표값은 최대 약 두 배가 듭니다. 목록의 길이가 전혀 필요 없으므로, 너무 길어서 잴 수 없거나 끝을 모르는 목록에서도 쓸 수 있습니다.

자주 묻는 질문

지수 탐색은 어떻게 동작하나요?

정렬된 목록에서 1, 2, 4, 8번째 자리 순으로 확인하다가 그 값이 목표값보다 작지 않으면 멈춥니다. 그러면 목표값은 마지막으로 확인한 두 자리 사이에만 있을 수 있으므로, 그 범위를 이진 탐색하면 찾을 수 있습니다.

지수 탐색이 이진 탐색보다 빠른가요?

목표값이 목록 앞쪽에 있다면 그렇습니다. i번째 자리의 목표값은 목록 길이와 상관없이 약 2 log₂ i번 비교하면 됩니다. 목표값이 끝쪽에 있다면 일반 이진 탐색이 최대 약 두 배 더 빠릅니다.

어디에 쓰이나요?

스트림이나 무한 수열처럼 길이를 모르거나 끝이 없는 목록을 탐색할 때, 그리고 다음 일치 항목이 대개 가까이 있는 정렬된 런(run)을 병합할 때 쓰입니다. Timsort의 갤러핑 모드도 같은 두 배 늘리기 아이디어를 씁니다.

왜 ‘지수’ 탐색이라고 부르나요?

확인하는 자리가 1, 2, 4, 8, 16처럼 앞의 두 배씩 지수적으로 커지기 때문입니다. 배증 탐색이나 갤러핑 탐색이라고도 합니다.

제 숫자가 어딘가로 전송되나요?

아니요. 탐색은 브라우저에서 실행되며, 마지막 설정은 이 브라우저의 로컬 저장소에 저장됩니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

편집기로 이동