보간 검색(Interpolation Search)이란?
보간 검색은 숫자 키 값을 기준으로 오름차순 정렬된 배열에서 특정 키(target)를 빠르게 찾아내는 탐색 알고리즘입니다. 이진 탐색(Binary Search)이 항상 배열의 중간 지점을 확인하는 것과 달리, 보간 검색은 찾으려는 값의 위치를 데이터의 분포를 기반으로 추정한다는 점이 큰 차이점입니다.
특히 값들이 균등하게(uniformly) 분포되어 있는 정렬된 배열에서는 평균적으로 O(log log n)의 시간 복잡도를 보여, 이진 탐색(O(log n))보다 더 빠른 성능을 낼 수 있습니다.
위치 추정 공식
보간 검색은 다음 공식을 사용해 탐색 위치(pos)를 계산합니다.
pos = lo + ((x - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]))
이 공식의 핵심 아이디어는 다음과 같습니다.
- 찾으려는 값(x)이 arr[hi]에 가까울수록 더 큰 pos 값을 반환합니다.
- 찾으려는 값(x)이 arr[lo]에 가까울수록 더 작은 pos 값을 반환합니다.
즉, 값의 실제 분포를 반영하여 탐색 범위를 지능적으로 좁혀 나가는 방식입니다.
공식에 사용되는 변수
- arr[] — 탐색 대상이 되는 정렬된 배열
- x — 찾고자 하는 요소(타깃 값)
- lo — 탐색 범위의 시작 인덱스
- hi — 탐색 범위의 끝 인덱스
자바스크립트 구현 예제
자바스크립트 함수는 첫 번째 인수로 숫자 배열을, 두 번째 인수로 검색할 타깃 값을 받습니다. 그리고 보간 검색 알고리즘을 활용해 해당 요소의 인덱스를 반환하며, 요소가 존재하지 않으면 -1을 반환합니다.
다음은 전체 구현 코드입니다.
const arr = [1, 4, 6, 7, 9, 12, 15, 16, 17, 23, 25, 26, 27, 31];
const target = 25;
const interpolationSearch = (arr = [], target) => {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const rangeDelta = arr[right] - arr[left];
const indexDelta = right - left;
const valueDelta = target - arr[left];
// 타깃이 현재 범위보다 작으면 존재하지 않음
if (valueDelta < 0) {
return -1;
}
// 범위 내 값이 모두 같은 경우
if (!rangeDelta) {
return arr[left] === target ? left : -1;
}
// 보간 공식으로 중간 위치 추정
const middleIndex = left + Math.floor((valueDelta * indexDelta) / rangeDelta);
if (arr[middleIndex] === target) {
return middleIndex;
}
if (arr[middleIndex] < target) {
left = middleIndex + 1;
} else {
right = middleIndex - 1;
}
};
return -1;
};
console.log(interpolationSearch(arr, target));실행 결과
위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.
10
배열에서 값 25는 인덱스 10(0부터 시작)에 위치하므로, 함수가 올바르게 10을 반환한 것을 확인할 수 있습니다.
마무리 및 참고 사항
보간 검색은 데이터가 균등하게 분포되어 있을 때 매우 효율적이지만, 분포가 심하게 치우친 경우 최악에는 O(n)까지 성능이 저하될 수 있습니다. 또한 이 코드에는 0으로 나누기 오류를 방지하기 위해 rangeDelta가 0인 경우를 처리하는 로직이 포함되어 있다는 점도 주목할 만합니다. 정렬된 균등 분포 데이터를 다룬다면 이진 탐색 대신 보간 검색을 고려해볼 만한 좋은 선택지입니다.