보간 탐색이란?

· 정렬이 이미 되어 있는 리스트에서 탐색키가 존재할 위치를 예측하여 탐색하는 방법. (사전에서 'ㄱ'으로 시작되는 단어가 앞에 있을 거라고 생각하고 앞 부분을 찾는 것과 같은 원리)

· 이진 탐색과 유사하나 리스트를 반으로 분할하지 않고 불균등하게 분할하여 탐색함. (이진 탐색의 업그레이드 버전?)

보간 탐색의 index값 구하는 공식

이진 탐색에서 mid값 구하는 공식과는 다름.

보간 탐색의 장점

· 많은 데이터가 비교적 균등하게 분포되어 있을 경우 보간 탐색은 이진 탐색보다 더 효율적일 수 있음.

시간 복잡도

보간 탐색 코드(Java)

public int interpolationSearch(int[] arr, int key, int low, int high) {
	int index = 0;
	
	while(low < high) {
		if(key < arr[low] || key > arr[high]) {
			return -1;
		} 
			
		index = low + (key - arr[low]) * ((high - low)) / (arr[high] - arr[low]);
			
		if(key == arr[index]) {
			return index;
		} else if(key < arr[index]) {
			high = index - 1;
		} else {
			low = index + 1;
		}
	}
		
	return -1;
}