검색 (5) - 내분 검색 (Interpolation Search)

1. 알고리즘 개요 

• 데이터가 선형의 형태(y = wx + b)로 정렬되었다고 가정하고 선형보간을 실시하여 Key가 실제로 있을법한 위치를 빠르게 찾아내는 방법

• 만약 데이터가 선형의 분포라면 아래 그림에서 삼각형의 비례식 (R-L) : (M-L) = (a[R] - a[L]) : (key - a[L])을 따르게 된다. (밑변이 R~L, 빗변이 a[R]~a[L]인 삼각형을 놓고 생각하자)

• mid 계산만 선형보간으로 실시하고, 나머지 방법은 Binary Search와 동일하다.

 

 

2. 소스코드 (검색 부분만 첨부함. 나머지 Binary Search와 동일)

public Integer get(int val) {
    return interpolationSearch(array, val, 0, count - 1);
}

private Integer interpolationSearch(Integer[] arr, int val, int l, int r) {
// 데이터 분포가 Linear하다고 가정하고 Linear Interpolation 실시

    if (l <= r) {
        int mid = l + (r - l) * (val - arr[l]) / (arr[r] - arr[l]);
        // 선형에 가까울수록 오차가 적어져서 더 빨리 탐색 가능
            
        if (arr[mid] == val)
            return arr[mid];

        if (arr[mid] < val)
            return interpolationSearch(arr, val, mid + 1, r);
        else
            return interpolationSearch(arr, val, 0, mid - 1);
    } else
        return null;
}

 

3. Reference