탐색 (Search) : 보간 탐색 (Interpolation Search)

원리

---

이진 탐색에서 사용한 중앙부터 탐색하는 것이 아닌 선형 보간법(linear interpolation)을 이용한 탐색 방법입니다. 선형 보간법이란 어떠한 두 점 사이에 위치한 한 점을 추정하기 위해 선형적으로 계산하는 방법입니다.

위 그래프에서 $(x, y)$를 구하면 이진 탐색에서 사용한 중앙점 대신 다른 한 점이 나오게 됩니다. $(x, y)$를 구하기 위해서는 $(x, y)$과의 비례 관계를 구해야합니다. 위 그래프에서 세 점의 비례 관계는 $\frac{y-y_0}{x-x_0} = \frac{y_1-y_0}{x_1-x_0}$입니다. 즉, y에 대한 식으로 바꾸면 다음과 같습니다. $$y = y_{0} + (y_1 - y_0)\frac{x-x_0}{x_1-x_0}$$

위 식이 바로 알려진 두 점 사이에서 구한 추정되는 점입니다. 이 점을 이용하여 탐색을 진행할 수 있습니다.

소스 코드 (구현)

---

#include <iostream>

using namespace std;

template <typename T>
T *interpolation_search(T *start, T *end, const T &target)
{
    if(*start > target || *end < target)
        return nullptr;

    T *mid = ((target - *start) / (*end - *start) * (end - start)) + start;

    if(*mid == target)
        return mid;
    else if(target < *mid)
        return interpolation_search(start, mid - 1, target);
    else
        return interpolation_search(mid + 1, end, target);
}

int main()
{
    int arr[] = {1, 3, 4, 7, 9};
    int *result;

    result = interpolation_search(arr, arr + 4, 2);

    if(result == nullptr)
        cout << "ERROR: Search Fail" << endl;
    else
        cout << *result << endl;

    return 0;
}