이진 탐색(Binary Search)은 리스트를 항상 동일한 크기의 부분으로 나누어가며 탐색을 진행합니다. 반면 보간 검색(Interpolation Search)은 보간 공식(Interpolation Formula)을 활용해 찾고자 하는 값의 예상 위치를 직접 계산하는 방식입니다. 예상 위치를 먼저 파악한 후, 그 위치를 기준으로 리스트를 분할하여 탐색 범위를 좁혀 나갑니다.
매 단계마다 키가 있을 만한 정확한 위치를 추정하기 때문에 탐색 시간이 크게 단축됩니다. 특히 데이터가 균등하게 분포(uniformly distributed)되어 있다면 매우 빠르고 효율적으로 원하는 항목을 찾을 수 있습니다.
보간 검색의 시간 및 공간 복잡도
- 시간 복잡도: 평균적인 경우 O(log₂(log₂ 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
출력:
Item found at location: 16
보간 검색 알고리즘
interpolationSearch(array, start, end, key)
입력 − 정렬된 배열, 시작 위치(start), 끝 위치(end), 그리고 탐색할 키(key)
출력 − 키를 찾은 경우 해당 위치(index), 찾지 못한 경우 유효하지 않은 위치(-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
EndC++ 구현 예제
아래는 위 알고리즘을 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 << "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 = interpolationSearch(arr, 0, n-1, 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
정리
보간 검색은 정렬된 배열에서 데이터가 균등하게 분포되어 있을 때 이진 탐색보다 훨씬 빠른 성능을 보이는 탐색 기법입니다. 선형 보간 공식을 통해 키의 위치를 예측하므로 평균적으로 O(log log n)의 시간 복잡도를 가지며, 추가 메모리가 거의 필요하지 않다는 장점이 있습니다. 다만 데이터 분포가 불균등한 경우 성능이 저하될 수 있으므로, 데이터의 분포 특성을 고려하여 적절히 활용하는 것이 중요합니다.