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