Interpolation Search

보간 탐색(Interpolation Search)은 이진 탐색의 변형으로, 특정 값의 위치를 예측하여 탐색하는 알고리즘입니다.

이진 탐색이 중간값(mid)을 기준으로 배열을 나누는 반면, 보간 탐색은 배열의 값 분포를 고려하여 탐색할 위치를 추정합니다.

실생활에서 자주 사용이 되는데 예를 들어, ‘홍길동’이라는 이름을 찾고자 할 때 대부분의 사람들은 중간값(‘ㅅ’)을 기준으로 하지 않고, ‘ㅎ’ 페이지를 펼쳐보는 것과 동일합니다.

보간 탐색의 과정

---

보간탐색을 진행하기 전에 pos를 구해야하는데

다음은 보간 탐색의 위치를 계산하는 공식입니다:

•	arr[]: 탐색할 데이터가 담긴 배열
•	x: 탐색할 값
•	low: 배열의 시작 인덱스
•	high: 배열의 끝 인덱스

이 공식은 arr 배열의 값이 선형적으로 증가한다고 가정하여, x의 위치를 예측합니다.

이렇게 pos를 구하면 보간 탐색이 이루어지는데 그 과정은

1. 위치 계산: 반복문을 통해 위의 공식을 사용하여 pos 값을 계산합니다.

2. 일치 여부 확인: pos 위치의 값이 x와 같으면 해당 인덱스를 반환하고 종료합니다.

3. 서브 배열 탐색: arr[pos]가 x보다 작으면 오른쪽 서브 배열로 이동하고, 크면 왼쪽 서브 배열로 이동하여 탐색을 계속 진행합니다.

4. 반복: 일치하는 값을 찾거나 서브 배열의 크기가 0이 될 때까지 2, 3번의 과정을 반복합니다.

구현

---

// 보간 탐색 구현 (재귀 방식)
#include <stdio.h>

// x가 arr[0..n-1]에 존재하면 인덱스를 반환, 그렇지 않으면 -1을 반환
int interpolationSearch(int arr[], int lo, int hi, int x)
{
   int pos;
   
   // 탐색할 범위가 유효하고 x가 해당 범위 내에 있을 때만 탐색
   if (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
      // 보간 탐색을 위한 위치 계산
      pos = lo + ((x - arr[lo]) * (hi - lo)) / (arr[hi] - arr[lo]);

      // x를 찾았을 경우 해당 인덱스 반환
      if (arr[pos] == x)
         return pos;

      // x가 더 큰 경우 오른쪽 서브 배열로 이동
      if (arr[pos] < x)
         return interpolationSearch(arr, pos + 1, hi, x);

      // x가 더 작은 경우 왼쪽 서브 배열로 이동
      if (arr[pos] > x)
         return interpolationSearch(arr, lo, pos - 1, x);
   }
   return -1; // x가 배열 내에 존재하지 않는 경우
}

// 실행 코드
int main()
{
   // 검색할 배열
   int arr[] = { 10, 12, 13, 16, 18, 19, 20, 21,
            22, 23, 24, 33, 35, 42, 47 };
   int n = sizeof(arr) / sizeof(arr[0]);

   int x = 18; // 탐색할 값
   int index = interpolationSearch(arr, 0, n - 1, x);

   // 결과 출력
   if (index != -1)
      printf("값을 찾았습니다. 인덱스: %d", index);
   else
      printf("값을 찾지 못했습니다.");
   return 0;
}

성능 분석

---

• 시간 복잡도: 평균적으로 $O(\log_2(\log_2 n))$의 성능을 보이며, 최악의 경우 $O(n)$의 시간 복잡도를 가집니다.
  최악의 경우는 배열이 불균일하게 분포되어 있을 때 발생합니다.

• 보조 공간 복잡도: $O(1)$

장점

---

• 빠른 탐색: 데이터가 균일하게 분포되어 있는 경우 매우 빠르게 값을 찾을 수 있습니다.

• 효율적인 계산: 기존 이진 탐색보다 더 빠른 경우가 많으며, 선형 분포에 가까운 데이터에서 유리합니다.

단점

---

• 불균일한 분포에 취약: 데이터가 불균일하게 분포된 경우에는 성능이 급격히 저하될 수 있습니다.

• 정렬된 배열에만 사용 가능: 보간 탐색은 정렬된 배열에서만 사용할 수 있으며, 배열이 정렬되지 않은 경우 사용할 수 없습니다.

정리

---

보간 탐색은 배열이 균등하게 분포되어 있을 때 이진 탐색보다 효율적일 수 있는 알고리즘입니다.
그러나 배열이 불균형하게 분포된 경우 성능이 떨어질 수 있으므로, 배열의 특성을 고려하여 적절히 사용해야 합니다.