이진 탐색(binary search)은 탐색 범위를 항상 절반씩 균등하게 나누며 진행합니다. 반면 보간 검색(interpolation search)은 보간 공식을 활용해 찾고자 하는 값이 있을 만한 위치를 직접 추정합니다. 추정한 위치를 기준으로 리스트를 다시 나누어 탐색 범위를 좁혀 나가기 때문에, 매 단계마다 실제 위치에 가장 가까운 곳을 찾으려 시도하게 되고 그만큼 탐색 시간이 크게 단축됩니다. 특히 데이터가 균등하게 분포(uniformly distributed)되어 있을 때 이 기법은 매우 빠르게 원하는 항목을 찾아냅니다.
보간 검색에서 위치를 추정하는 공식은 다음과 같습니다.
pos = start + ((key − array[start]) × (end − start)) / (array[end] − array[start])
보간 검색 기법의 복잡도
시간 복잡도: 평균적인 경우 O(log2(log2 n)), 최악의 경우 O(n) — 데이터가 지수적으로 분포되어 있을 때 해당
공간 복잡도: O(1)
입력 − 정렬된 데이터 목록 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995 탐색 키: 780 출력 − 위치 16에서 항목을 찾음
알고리즘
interpolationSearch(array, start, end, key)
입력: 정렬된 배열, 시작 위치(start)와 끝 위치(end), 탐색 키(key)
출력: 키가 존재하면 해당 위치, 존재하지 않으면 유효하지 않은 위치(-1)
Begin
while start <= end AND key >= array[start] AND key <= array[end] do
dist := key – array[start]
valRange := array[end] – array[start]
fraction := dist / valRange
indexRange := end – start
estimate := start + (fraction * indexRange)
if array[estimate] = key then
return estimate position
if array[estimate] < key then
start := estimate + 1
else
end := estimate - 1
done
return invalid position
End
C++ 예제 코드
#include<iostream>
using namespace std;
int interpolationSearch(int array[], int start, int end, int key) {
int dist, valRange, indexRange, estimate;
float fraction;
while(start <= end && key >= array[start] && key <= array[end]) {
dist = key - array[start];
valRange = array[end] - array[start]; //값의 범위
fraction = dist / valRange;
indexRange = end - start;
estimate = start + (fraction * indexRange); //탐색 키의 추정 위치
if(array[estimate] == key)
return estimate;
if(array[estimate] < key)
start = estimate + 1;
else
end = estimate - 1;
}
return -1;
}
int main() {
int n, searchKey, loc;
cout << "항목 개수를 입력하세요: ";
cin >> n;
int arr[n]; //크기가 n인 배열 생성
cout << "항목들을 입력하세요:" << endl;
for(int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "탐색할 키를 입력하세요: ";
cin >> searchKey;
if((loc = interpolationSearch(arr, 0, n-1, searchKey)) >= 0)
cout << "위치 " << loc << "에서 항목을 찾았습니다." << endl;
else
cout << "목록에서 항목을 찾지 못했습니다." << endl;
}
참고: int arr[n];처럼 실행 시점에 크기를 결정하는 가변 길이 배열(VLA)은 C++ 표준에는 포함되지 않으며, GCC나 Clang 같은 일부 컴파일러의 확장 기능으로 동작합니다. 표준 C++을 엄격히 준수하려면 std::vector<int>를 사용하는 것이 좋습니다.
실행 결과
항목 개수를 입력하세요: 20 항목들을 입력하세요: 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995 탐색할 키를 입력하세요: 780 위치 16에서 항목을 찾았습니다.
보간 검색은 데이터가 고르게 분포된 대규모 정렬 배열에서 이진 탐색보다 적은 비교 횟수로 원소를 찾을 수 있는 강력한 기법입니다. 다만 데이터 분포가 크게 치우쳐 있으면 성능이 O(n)까지 저하될 수 있으므로, 실제 적용 전에 데이터의 분포 특성을 먼저 파악하는 것이 좋습니다.