보간탐색(Interpolation Search)

선형탐색(Linear Search)는 데이터의 원소를 처음부터 끝까지 순차적으로 탐색하면서 검색하는 부르트포트(Brute Force)의 종류이고

이진탐색(Binary Search)은 정렬된 데이터 원소들을 절반씩 나누면서 분할 정복(Divide Conquer)하는 방식이라고 설명했었다.

그럼 보간탐색(Interpolation Search)은 무엇인가?

보간탐색은 이진탐색을 개선한 것인데 이진탐색처럼 비교 대상을 무조건 mid = (high-low)/2 로 하지 않고 우리가 찾는 원소는 전체 데이터 값을 보니 대충 이정도에 있겠구나 추측하여 탐색하는 방식이다.

 

예를들어 data = [2, 4, 6, 8, 10, 12, 14] 가 있고 이중 12를 찾는다면 이진탐색은 mid = (6 - 0)/2 = 3이 되어 data[3]  = 8부터 탐색 대상이 되지만 보간탐색에서는 mid = low + ((high - low) / (data[high] - data[low])) * (12 - data[low]) 공식을 이용하여 mid 값을 결정한다,

위 공식이 도대체 어디서 튀어 나왔는지 살펴보자.

 

일단 선형 1차 함수(linear function)함수 y  = f(x) 가 아래와 같다고 하자

 

 

y1 = f(x1) 인 (x1, y1) 그리고 y2 = f(x2) 인 (x2, y2)   2개의 점이 주어 지고 (여기서 x1 < x2 )

 

 

y = f (x)와 같은 y의 주어진 값에 대해 x1 <= x <= x2 인 x를 찾으려고 한다면  우리는 삼각법(trigonometry)을 사용하면 가능하다.

 

 

위의 그림에서 알 수 있듯이 △ABC에 대한 tan𝛳의 값은 △ADE에 대한 tan𝛳의 값과 같고 삼각법에서 tan𝛳에 대한 공식은 아래와 같습니다.

 

tan𝛳 = a/b 이므로 △ABC 에 대한 tan𝛳 = y2-y1 / x2 - x1 으로 △ADE에 대한 tan𝛳 = y-y1 / x - x1 이 됩니다.

두  𝛳 값은 동일하니 (y2-y1) / (x2 - x1) = (y-y1) / (x - x1) 이고 다음과 같은 공식이 유도 됩니다.

 

y = y1 + (y2 - y1) * (x - x1) / (x - x1) or x = x1 + (x2 - x2) * (y - y1) / (y2 - y1) 

 

이 공식이 보간탐색을 위한 mid 값을 찾는데 어떻게 도움을 줄수 있는지 알아보자.

만약 입력 배열을 함수  f(x) 로 간주하면

x1 => low and y1 => array[low]
x2 => high and y2 => array[high]
x => pos and y => array[pos] i.e. key.

이 값을 위 공식에 대입하면 최종적으로 보간탐색을 위한 공식이 된다.

 

 

 

주의할 점은 보간탐색은 찾는 대상을 비례적으로 찾기 때문에 데이터가 균등하게 분포(uniformly distributed)되어 있는 자료에 적합하다.

일종의 등비, 등차수열 같은 자료라면 이진탐색보다 보간탐색을 사용하여 원소를 찾는게 더 효율적이다.

보간탐색의 성능은 만약 데이터가 균등하게 분포되어 있다면  O (log log n) 이고 최악의 경우 O(n) 이다.

구현 코드는 mid 가 이진탐색 처럼 데이터의 1/2 이 아니 위 공식을 대입하여 구하면되고 나머지는 거의 비슷하다.

 

 
public class Main {
 
    public static void main(String[] args) {
        int array[] = new int[]{10, 12, 13, 16, 18, 19, 20, 21, 22, 23,
                24, 33, 35, 42, 47};
 
 
        System.out.println(interpolationSearch(array, 16)); // 3
        System.out.println(interpolationSearch(array, 22)); // 8
        System.out.println(interpolationSearch(array, 42)); // 13
        System.out.println(interpolationSearch(array, 36)); // - 14
    }
 
 
    public static  int interpolationSearch(int []array, int key) {
        // 맨처음 low = 0, high는 배열의 끝이다.
        int low = 0;
        int high = array.length - 1;
 
        // key 값은 반드시 list[low] <= key <= list[high] 범위에 있어야 한다.
        while (low <= high && key >= array[low] && key <= array[high]) {
 
            int pos = low + (((high-low) /
                    (array[high]-array[low]))*(key - array[low]));
 
            if (key > array[pos]) // 키값이 더 크면 왼쪽을 버린다.
                low = pos + 1;
            else if (key < array[pos]) // 키값이 더 작으면 오른쪽을 버린다.
                high = pos - 1;
            else
                return pos; // key found
        }
        return -(low + 1);  // key not found
    }
 
}
 
 

 

 

레퍼런스

▷ wikipedia - 삼각함수

▷ 보간탐색 공식 유도