[자료구조] 보간 탐색(Interpolation Search

보간 탐색은 이진탐색과 유사하다.

이진 탐색은 정렬된 배열의 중앙에 위치한 데이터를 기준으로 탐색을 시작한다.

보간탐색은 이런한 방식에서 발생할 수 있는 비효율을 줄이기 위해 등장하였다.

 

탐색 기준 선정방식

중복된 키가 없이 정렬된 데이터 들에 대한 탐색이라는점을 고려하여 탐색할 대상이 대략적으로 어디에 위치해 있는지를 파악하는 식이 존재한다.

이는 데이터의 값과 그 데이터가 저장된 위치의 인덱스값이 비례하다는 생각을 근거를 기반에 두고있다.

 

"x" 라는 데이터를 찾는 경우, 해당 데이터의 인덱스 값 "s"에 대한 식은 다음과 같다.

 

low : 탐색 대상의 시작 인덱스

high : 탐색 대상의 마지막 인덱스

 

#include <stdio.h>

int ISearch(int ar[], int first, int last, int target) {
    int mid;

  //탈출 조건
    if(ar[first] > target || ar[last] < target) {
        return -1;
    }

    //보간 탐색의 비례관계 계산 식
    mid = ((double) (target - ar[first]) / (ar[last] - ar[first]) * (last - first)) + first;

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

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int idx;

  //7 찾기
    idx = ISearch(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1, 7);
    if(idx == -1)
        printf("탐색 실패\n");
    else
        printf("탐색 저장 인덱스 : %d\n", idx);

  //10 찾기
    idx = ISearch(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1, 10);
    if(idx == -1)
        printf("탐색 실패\n");
    else
        printf("탐색 저장 인덱스 : %d\n", idx);

    return 0;
}

 

 

 

참고 링크 : https://velog.io/@roycewon/보간-탐색법