보간 탐색

보간 탐색은 정렬된 배열에서 특정 값을 찾기 위한 탐색 알고리즘으로, 탐색키가 존재할 위치를 예측하여 탐색하는 방법이다.

보간 탐색은 이진 탐색과 유사하나 리스트를 반으로 분할하지 않고 불균등하게 분할하여 탐색한다. 배열은 항상 정렬되어 있어야 한다.

탐색 위치 공식

이진 탐색에서 탐색 위치는 항상 (low + high)/2이나, 보간 탐색에서는 찾고자하는 키값과 현재의 low, high 위치의 값을 고려하여 다음의 위치 공식을 사용하여 탐색 위치를 결정한다.

$\text{pos} = \text{low} + \left( \frac{\text{key} - \text{list}[\text{low}]}{\text{list}[\text{high}] - \text{list}[\text{low}]} \right) \times (\text{high} - \text{low})$

• pos: 예상되는 값의 위치
• low: 현재 탐색 범위의 시작 인덱스
• high: 현재 탐색 범위의 끝 인덱스
• list[low]: 현재 탐색 범위의 시작 값
• list[high]: 현재 탐색 범위의 끝 값
• key: 탐색하려는 값

위의 식은 탐색 위치를 결정할 때 찾고자 하는 키 값이 있는 곳에 근접하게 되도록 가중치를 주는 것이다. 위의 식은 다음의 비례식을 정리한 것으로 생각할 수 있다. 즉 값과 위치는 비례한다는 가정에서 탐색키에 해당하는 위치를 비례식으로 구한 것이다.

동작 과정

1. 배열이 정렬되어 있는지 확인
2. log, high 범위를 초기화(low = 0, high = n-1)
3. 위치 공식을 사용해 pos를 계산
4. list[pos]와 탐색 값을 비교
   • list[pos] == key: 탐색 성공, pos 반환
   • list[pos] < key: low = pos + 1로 이동
   • list[pos] > key: high = pos - 1로 이동
5. 값을 찾거나 탐색 범위가 low > high가 될 때까지 반복

장점과 단점

장점

• 데이터가 균등하게 분포되어 있는 경우, 이진 탐색보다 더 빠른 성능을 보임

단점

• 데이터가 균등하게 분포되지 않은 경우, 이진 탐색보다 성능이 떨어진다.
• 계산이 이진 탐색보다 복잡하며, 추가 연산이 필요하다.

시간 복잡도

불균등하긴 하지만, 계속해서 반으로 나누면 탐색 범위를 좁혀나가기 때문에 시간 복잡도는 $O(logn)$이다.

전체 코드

#include <stdio.h>

#define MAX_SIZE 1000
int list[MAX_SIZE];

init_list()
{
	int i;
	for(i=0;i<1000;i++)
		list[i] = 7*i;
}
int search_interpolation(int key, int n)
{
     int low, high, j;
     low = 0;
     high = n-1;
	 while ((list[high] >= key) && (key > list[low])){
          j = ((float)(key-list[low]) / (list[high]-list[low]) *
                         (high-low) ) + low;
          if( key > list[j] ) low = j+1;
          else if (key < list[j]) high = j-1;
          else low  = j;
	 }
     if (list[low] == key) return(low);  //found(r[low])
     else return -1;  // notfound(key)
}

//
void main()
{
		int i =0;
		init_list();
		i = search_interpolation(49, 0, 999);
		if( i >= 0 ) {
			printf("탐색 성공 i=%d\n", i);
		}
		else {
			printf("탐색 실패\n");
		}
}

출처
C언어로 쉽게 풀어쓴 자료구조 - 천인구