[자료구조] 보간 탐색 (interpolation search)

보간 탐색이란?

보간이라는 어휘가 생소해 사전에서 찾아봤습니다.

요약하자면, 몇 가지 알려져있는 함숫값으로 임의의 값을 추정하는 탐색 기법임을 알 수 있습니다. 말로만 들으면 생소하다고 생각됩니다. 자세한 건 아래 그림과 함께 살펴보겠습니다.

 

보간 탐색에서는 찾고 싶은 $key$값과 $low$, $high$ 값을 고려해 $pos$(탐색 위치)를 결정합니다.

 

위의 그림을 수식으로 표현하면 다음과 같습니다.

 

pos에 대한 식으로 변경해보겠습니다.

$$ pos = {(high - low) \times (k - list[low]) \over list[high] - list[low]} + low $$

 

코드로 구현하면 다음과 같습니다.

int interpol_search(int key, int n) {
	int low = 0, high = n - 1;
	while((list[high] >= key) && (key > list[low])) {
		int 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);
	else return -1;
}

 

보간 탐색 시간복잡도

보간 탐색의 시간복잡도는 평균적인 경우에는 $O(log (log\space n))$이고, 최악의 경우에는 $O(n)$입니다.