지수 검색(Exponential Search)이란?
지수 검색은 더블링 검색(doubling search) 또는 갤러핑 검색(galloping search)이라고도 불리는 탐색 기법으로, 정렬된 배열에서 원하는 값을 효율적으로 찾는 데 사용됩니다. 이 알고리즘의 핵심 아이디어는 처음부터 전체 배열을 탐색하는 것이 아니라, 찾고자 하는 키(검색값)가 존재할 가능성이 있는 범위(range)를 먼저 좁히는 것입니다.
리스트의 하한을 L, 상한을 U라고 할 때, L과 U는 모두 2의 거듭제곱 값을 가집니다. 마지막 구간에서는 U가 리스트의 마지막 위치가 되며, 인덱스가 2배씩 지수적으로 증가하는 방식으로 동작하기 때문에 '지수(exponential)' 검색이라는 이름이 붙었습니다.
적절한 범위를 찾은 후에는 이진 탐색(binary search) 기법을 적용하여 탐색 키의 정확한 위치를 확인합니다.
지수 검색의 복잡도
- 시간 복잡도: 최선의 경우 O(1), 평균 및 최악의 경우 O(log₂ i) — 여기서 i는 탐색 키가 존재하는 위치입니다.
- 공간 복잡도: O(1)
지수 검색은 특히 탐색 대상이 배열의 앞쪽에 가까울 때 일반 이진 탐색보다 빠르게 결과를 찾을 수 있으며, 크기를 미리 알 수 없는 배열이나 무한 스트림 데이터를 다룰 때 유용하게 활용됩니다.
입력과 출력
입력: 정렬된 데이터 리스트: 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995 탐색 키: 780 출력: Item found at location: 16
알고리즘
binarySearch(배열, start, end, key)
입력: 정렬된 배열, 시작·끝 위치, 탐색 키
출력: 키를 찾으면 해당 위치, 찾지 못하면 유효하지 않은 위치(-1)
Begin
if start <= end then
mid := start + (end - start) / 2
if array[mid] = key then
return mid // 키 발견, 위치 반환
if array[mid] > key then
call binarySearch(array, start, mid-1, key) // 왼쪽 절반 탐색
else if array[mid] < key then
call binarySearch(array, mid+1, end, key) // 오른쪽 절반 탐색
else
return invalid location
End
exponentialSearch(배열, start, end, key)
입력: 정렬된 배열, 시작·끝 위치, 탐색 키
출력: 키를 찾으면 해당 위치, 찾지 못하면 유효하지 않은 위치(-1)
Begin
if (end – start) <= 0 then
return invalid location
i := 1
while i < (end - start) do
if array[i] < key then
i := i * 2 // i를 2의 거듭제곱 형태로 증가
else
terminate the loop // array[i]가 키 값을 넘어서면 반복 종료
done
call binarySearch(array, i/2, i, key) // 좁혀진 범위 내에서 이진 탐색 수행
End
C++ 구현 예제
#include<iostream>
using namespace std;
int binarySearch(int array[], int start, int end, int key) {
if(start <= end) {
int mid = (start + (end - start) / 2); // 리스트의 중간 위치
if(array[mid] == key)
return mid;
if(array[mid] > key)
return binarySearch(array, start, mid-1, key);
return binarySearch(array, mid+1, end, key);
}
return -1;
}
int exponentialSearch(int array[], int start, int end, int key){
if((end - start) <= 0)
return -1;
int i = 1; // 2^0 = 1
while(i < (end - start)){
if(array[i] < key)
i *= 2; // i를 2의 거듭제곱 형태로 증가
else
break; // array[i]가 키 값을 넘어서면 반복 종료
}
return binarySearch(array, i/2, i, key); // 축소된 범위에서 항목 탐색
}
int main() {
int n, searchKey, loc;
cout << "Enter number of items: ";
cin >> n;
int arr[n]; // 크기 n인 배열 생성
cout << "Enter items: " << endl;
for(int i = 0; i< n; i++) {
cin >> arr[i];
}
cout << "Enter search key to search in the list: ";
cin >> searchKey;
if((loc = exponentialSearch(arr, 0, n, searchKey)) >= 0)
cout << "Item found at location: " << loc << endl;
else
cout << "Item is not found in the list." << endl;
}
실행 결과
Enter number of items: 20 Enter items: 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995 Enter search key to search in the list: 780 Item found at location: 16