지수 탐색

이진 탐색은 가운데를 보려면 먼저 목록이 어디서 끝나는지 알아야 합니다. 지수 탐색은 그럴 필요가 없습니다. 목표값을 지나칠 때까지 점점 더 큰 보폭으로 앞으로 내달린 뒤, 마지막 한 걸음 구간을 이진 탐색합니다. 그래서 길이를 모르는 목록에 안성맞춤이고, 앞쪽 값도 빨리 찾습니다.

정렬된 막대 한 줄. 1, 2, 4, 8번째 자리를 길이가 두 배씩 늘어나는 점프로 건너뛰고, 마지막 두 점프 사이의 범위가 음영으로 표시되어 있다
정렬된 막대 한 줄. 1, 2, 4, 8번째 자리를 길이가 두 배씩 늘어나는 점프로 건너뛰고, 마지막 두 점프 사이의 범위가 음영으로 표시되어 있다

핵심 아이디어

1번째 자리의 값을 확인하고, 이어서 2, 4, 8, 16번째 자리처럼 매번 앞 자리의 두 배인 자리를 확인합니다. 그 값이 목표값보다 작은 동안에는 목표값이 더 뒤에 있어야 합니다. 처음으로 작지 않은 값이 나오면 목표값은 갇힌 셈입니다. 직전에 확인한 자리 뒤에 있고, 이 자리보다 뒤에 있지는 않습니다. 그 범위는 정렬되어 있으므로 이진 탐색으로 목표값을 찾거나, 없다는 것을 알 수 있습니다.

예시

2, 5, 8, 12, 16, 23, 38, 56, 72, 91에서 23을 찾아봅시다. 1번째 자리는 2, 2번째는 5, 4번째는 12로 모두 작습니다. 8번째 자리는 56으로 더 크므로, 23은 5~7번째 자리에만 있을 수 있습니다. 이진 탐색이 그 가운데인 6번째 자리를 확인해 23을 찾습니다. 비교 5번이며, 일반 이진 탐색은 3번이 필요합니다. 같은 목록에서 12를 찾으면 비교 3번 만에 4번째 자리에서 멈춰 이진 탐색보다 한 번 적고, 2는 1번째 자리에서 비교 한 번 만에 찾습니다.

비교 횟수

i번째 자리의 목표값이라면 두 배로 늘리는 단계는 약 log₂ i번 만에 멈추고, 자리가 i개보다 적은 범위를 남기며, 이진 탐색이 이를 약 log₂ i번 더 들여 처리합니다. 따라서 목록 길이와 상관없이 약 2 log₂ i번의 비교가 듭니다. 목표값이 앞쪽에 있으면 항상 약 log₂ n번이 드는 이진 탐색보다 유리합니다. 끝쪽에 있으면 지수 탐색이 최대 약 두 배를 씁니다. 값 40개일 때 이 앱에서는 처음 다섯 자리는 평균 약 3번, 마지막 다섯 자리는 약 9번의 비교가 들고, 이진 탐색은 약 4.6번입니다.

길이를 모를 때, 그리고 갤러핑

Jon Bentley와 Andrew Yao는 1976년에 무한 탐색을 위해 이 두 배 늘리기 전략을 제시했습니다. 무한 목록이나 한 자리씩 들여다볼 수밖에 없는 스트림처럼 끝을 모르는 정렬된 수열에서 값을 찾는 문제입니다. 같은 아이디어로 병합도 빨라집니다. 두 정렬된 런 중 한쪽이 계속 이기면 Timsort는 갤러핑으로 전환합니다. 다음 값이 들어갈 곳을 찾으려고 다른 런에서 한 칸씩 나아가는 대신 1, 2, 4, 8칸 앞을 봅니다.

직접 해 보기

앱을 열고 ‘찾을 값’에서 값을 고른 뒤 ‘단계’를 누르세요. 1, 2, 4, 8번째 자리 등을 확인할 때마다 강조 표시되고, 작지 않은 값이 나오면 마지막 두 자리 사이의 범위가 음영으로 표시되며 이진 탐색이 이어받습니다. 작은 값과 큰 값을 차례로 찾아보고, 비교 횟수를 이진 탐색 타일과 비교해 보세요.

자주 묻는 질문

지수 탐색의 시간 복잡도는?

i번째 자리의 목표값이라면 O(log i)이므로, 값이 n개인 목록에서는 최대 O(log n)입니다. 추가 메모리는 O(1)이며 정렬된 목록이 필요합니다.

지수 탐색과 이진 탐색의 차이는?

이진 탐색은 목록 전체에서 시작하며 그 길이가 필요합니다. 지수 탐색은 먼저 두 배로 늘려 가며 목표값이 든 범위를 찾고, 그 범위만 이진 탐색합니다. 목표값이 앞쪽에 있을 때 더 빠르고, 길이를 몰라도 동작합니다.

왜 고정된 폭을 더하지 않고 보폭을 두 배로 늘리나요?

고정된 폭을 더하는 것은 점프 탐색으로, 목록을 가로지르려면 약 n을 폭으로 나눈 만큼 확인해야 합니다. 두 배로 늘리면 약 log₂ i번 만에 i번째 자리에 닿고, 남는 범위도 필요한 크기의 두 배를 넘지 않으므로 이어지는 이진 탐색도 짧습니다.

지수 탐색은 어디에 쓰이나요?

끝이 없거나 아주 긴 정렬된 데이터를 탐색할 때, 정렬된 런을 병합할 때(Timsort의 갤러핑), 그리고 상한을 모르는 상태에서 어떤 조건이 처음으로 참이 되는 자리를 찾을 때 쓰입니다.

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

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

지수 탐색 해 보기