[기초] C++ 보간 탐색 (Interpolation Search)

---

 

보간 탐색(Interpolation Search)은 선형적으로 분포된 정렬된 배열에서 특정 값을 찾는 알고리즘입니다.

보간 탐색은 이진 탐색과 유사하지만, 이진 탐색이 배열의 중간 요소를 기준으로 검색 범위를 줄이는 반면,

보간 탐색은 검색 값이 어디에 있을지 추정하여 더 효율적으로 검색 범위를 줄입니다.

이는 이진 탐색보다 평균적인 경우에 더 빠를 수 있지만, 최악의 경우 O(n)이 될 수 있습니다.

보간 탐색의 시간 복잡도는 일반적으로 O(log(log(n)))입니다.

 

---

 

동작 원리

 

• 배열이 정렬되어 있다는 가정 하에, 찾고자 하는 값의 위치를 추정하여 검색 범위를 줄입니다.
  
  
• 보간 공식을 사용하여 위치를 계산합니다
  'pos = low + ((x - arr[low]) * (high - low) / (arr[high] - arr[low]))'.
  
  
• 여기서 'x'는 찾고자 하는 값, 'low'와 'high'는 배열의 현재 검색 범위의 시작과 끝 인덱스입니다.
  
  

 

#include <iostream>

int interpolationSearch(int arr[], int size, int x) {
    int low = 0;
    int high = size - 1;

    while (low <= high && x >= arr[low] && x <= arr[high]) {
        if (low == high) {
            if (arr[low] == x) return low;
            return -1;
        }

        // 보간 공식
        int pos = low + ((double)(high - low) / (arr[high] - arr[low]) * (x - arr[low]));

        // 값이 발견된 경우
        if (arr[pos] == x) {
            return pos;
        }

        // x가 arr[pos]보다 큰 경우, 오른쪽 부분을 탐색
        if (arr[pos] < x) {
            low = pos + 1;
        }
        // x가 arr[pos]보다 작은 경우, 왼쪽 부분을 탐색
        else {
            high = pos - 1;
        }
    }
    return -1; // 값이 배열에 없는 경우
}

int main() {
    int arr[] = {10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47};
    int size = sizeof(arr) / sizeof(arr[0]);
    int x = 18; // 찾고자 하는 값

    int result = interpolationSearch(arr, size, x);
    if (result != -1) {
        std::cout << "Element found at index " << result << std::endl;
    } else {
        std::cout << "Element not found." << std::endl;
    }

    return 0;
}

 

출력값

 

Element found at index 4

 

프로세스 설명

 

• 'low'를 배열의 첫 번째 인덱스로, 'high'를 배열의 마지막 인덱스로 설정합니다.
  
  
• 'low'가 'high'보다 작거나 같은 동안 반복합니다.
  
  • 'arr[low]'와 'arr[high]'가 같으면 'low'와 'high'를 업데이트합니다.
  • 'pos'를 보간 공식에 따라 계산합니다.
  • 'arr[pos]'와 'x'를 비교합니다.
  • 'arr[pos]'가 'x'와 같으면 'pos'를 반환합니다.
  • 'arr[pos]'가 'x'보다 작으면 'low'를 'pos + 1'로 설정하여 검색 범위를 좁힙니다.
  • 'arr[pos]'가 'x'보다 크면 'high'를 'pos - 1'로 설정하여 검색 범위를 좁힙니다.
• 값이 발견되지 않으면 -1을 반환합니다.
  
  

마무리

 

정렬된 배열 'arr'에서 'x' 값을 찾기 위해 보간 탐색을 구현한 것입니다.

배열은 미리 정렬되어 있어야 하며, 찾고자 하는 값이 배열에 존재하는 경우 해당 값의 인덱스를 반환합니다.

찾고자 하는 값이 배열에 없는 경우 '-1'을 반환합니다.

이 알고리즘은 선형적으로 분포된 데이터에서 효율적으로 작동하며,

보간 공식을 사용하여 검색 범위를 줄이므로 평균적인 경우에 매우 빠른 검색이 가능합니다.

 

 

제 글이 도움이 되셨다면 댓글 & 공감 부탁드려요 😀