Chap11. 탐색 (Search), 보간 탐색 (Interpolation Search)

탐색은 알고리즘보다 자료구조에 가까운 주제라고 볼 수도 있다.

왜냐하면 사실상 이미 나열된 데이터들을 탐색하는데는 속도의 한계가 있다.

따라서 애초에 데이터를 저장할때 어떻게 저장할 것인지를 고민해야 한다. 

 

보간 탐색 (Interpolation Search) 

보간 (Interpolation) :

• 보간법(補間法)또는 내삽(內揷,interpolation)은 해석학에서 어떤 그래프 등의 자료에서 나와있는 부분의 사이에 있는 값을 평균하여 추정하는 것이다.

(출처: http://ko.wordow.com/english/dictionary/interpolation)

 

이진 탐색은 중앙에 위치한 데이터를 탐색하고 이를 기준으로 데이터의 크기를 반씩 줄여 나간다.

즉 찾는 대상이 어디에 위치하건 상관없이 무조건 중앙의 데이터를 골라서 비교해 나간다. 

따라서 찾는 데이터의 위치에 따라서 효율의 차이가 발생한다. 

찾는 데이터가 중간에 있다면 효율이 좋아지지만 양쪽 끝에 위치할수록 효율이 떨어진다.

 

보간 탐색은 이진 탐색의 이러한 단점을 개선한 탐색법이다. 

보간 탐색은 데이터가 위치한 대략적인 위치를 찾아서 그 위치에서 부터 탐색을 시작한다. 

이러한 특성 때문에 보간탐색은 사전이나 전화번호부에 비유된다.

 

---

보간 탐색의 탐색 위치 결정

그렇다면 보간 탐색은 탐색 위치를 결정하는 것이 핵심이라고 할 수 있을 것 같다.

보간 탐색에서는 데이터의 값과 그 데이터가 저장된 위치의 인덱스가 비례한다고 가정한다. (이런 데이터만 탐색할수 있다는 것이다) 

이렇게 가정하기 때문에 다음과 같은 비례식이 성립한다. 

 

low : 탐색 대상의 시작 지점 

high : 탐색 대상의 끝 지점 

s : 찾는 데이터의 인덱스 

 

 

위 비례식에서 A는 low에서 high까지, Q는 low에서 찾는 데이터 지점 s까지를 나타낸다.

데이터 값과 인덱스 위치가 비례하기 때문에 위와 같은 식이 성립한다. 

 

비례식을 찾는 데이터의 인덱스값 s에 대하여 정리하면 

 

A는 low에서 high까지 이기 때문에, A = arr[high] - arr[low] 이고, 

Q는 low에서 s까지 이기 때문에, Q = arr[s] - arr[low] 이므로 

 

위 식은 우리가 찾는 값을 arr[s] 에 삽입하여 탐색위치의 인덱스값 s를 구하는 식이다.

다시한번 말하지만 이런 비례식이 성립하는 이유는 보간탐색의 대상 배열이 데이터의 값과 저장 위치의 인덱스가 비례하기 때문이다.

그리고 이 식에서 이뤄지는 나눗셈은 정수형 나눗셈이 아닌 실수형 나눗셈이다. 

이는 오차율을 최소화하기 위해서이다. 

 

---

보간 탐색 구현

앞서 보간탐색과 이진탐색의 유일한 차이점은 탐색 위치를 선정하는 방법이라고 했다.

이진탐색은 중앙을, 보간 탐색은 비례식을 이용해 그 위치를 찾는다.

 

다음은 이진 탐색을 구현한 것이다.

int BSearchRecur(int ar[], int first, int last, int target)
{
    if(first > last) return -1;

    int mid = (first + last) / 2;

    if(ar[mid] == target)
        return mid;
    else if(target < ar[mid])
        return BSearchRecur(ar, first, mid-1, target);
    else
        return BSearchRecur(ar, mid+1, last, target);
}

 

다음은 보간 탐색이다.

#include <stdio.h>

int InterpolSearch(int ar[], int first, int last, int target)
{
	if(ar[first] > target || ar[last] < target) return -1;

    int targetIdx = ((double)(target-ar[first]) / (ar[last]-ar[first]) * (last-first)) + first;

    if(ar[targetIdx] == target)
        return targetIdx;
    else if(target < ar[targetIdx])
        return InterpolSearch(ar, first, targetIdx-1, target);
    else
        return InterpolSearch(ar, targetIdx+1, last, target);
}

int main()
{
    int arr[] = {1, 3, 5, 7, 9};
    int idx = InterpolSearch(arr, 0, 4, 3);
    if(idx == -1)
        printf("search failed\n");
    else
        printf("target idx: %d\n", idx);
}

 

보다시피 이진 탐색과 보간 탐색의 차이점은 targetIdx를 정하는 부분과, 재귀의 탈출 조건 뿐이다.

재귀의 탈출 조건이 위와 같은 이유는 first와 last 사이에 탐색대상이 존재하지 않을 경우, 동일한 전달 인자를 갖고 재귀하게 되며 무한 루프를 이루기 때문이다.