자료구조 - 보간 탐색

[보간 탐색 (Interpolation Search)]

보간 탐색은 이진 탐색과 유사하지만, 탐색할 값을 예상 위치로 바로 접근하여 탐색 속도를 향상시키는 알고리즘입니다.

보간 탐색은 데이터가 균등하게 분포되어 있는 경우 특히 효과적입니다.

 

보간 탐색 작동 원리

1. 배열의 시작 인덱스와 끝 인덱스를 설정합니다.
2. 현재 탐색 범위 내에서 찾고자 하는 값이 있을 것으로 예상되는 위치를 계산합니다.
3. 계산된 위치의 값과 찾고자 하는 값을 비교하여 찾고자 하는 값이 현재 위치보다 작으면 왼쪽 부분을, 크면 오른쪽 부분을 탐색합니다.
4. 값을 찾을 때까지 또는 탐색 범위가 없을 때까지 이 과정을 반복합니다.

위치 계산 공식

 

 

 

보간 탐색 의사 코드

함수 interpolationSearch(arr, n, key):
    low = 0
    high = n - 1

    while low <= high and key >= arr[low] and key <= arr[high]:
        if low == high:
            if arr[low] == key:
                반환 low
            반환 -1

        pos = low + ((key - arr[low]) * (high - low) / (arr[high] - arr[low]))

        if arr[pos] == key:
            반환 pos
        if arr[pos] < key:
            low = pos + 1
        else:
            high = pos - 1

    반환 -1

 

 

 

보간 탐색 예제

정렬된 배열: [10, 20, 30, 40, 50]
찾고자 하는 값: 40

1. 초기 상태:
    low = 0, high = 4
    arr = [10, 20, 30, 40, 50]

2. 첫 번째 반복:
    pos = 0 + ((40 - 10) * (4 - 0) / (50 - 10)) = 0 + (30 * 4 / 40) = 3    
    arr[3] = 40
    40을 찾음

 

 

 

보간 탐색 코드

#include <iostream>
#include <vector>

using namespace std;

// 보간 탐색 함수
int interpolationSearch(const vector<int>& arr, int key) {
    int low = 0;
    int high = arr.size() - 1;

    while (low <= high && key >= arr[low] && key <= arr[high]) 
    {
        // low와 high가 같은 경우, arr[low]를 반환
        if (low == high) 
        {
            if (arr[low] == key) 
            {
                return low;
            }
            return -1;
        }

        // 예상 위치 계산
        int pos = low + ((key - arr[low]) * (high - low) / (arr[high] - arr[low]));

        // 찾고자 하는 값을 찾은 경우
        if (arr[pos] == key) 
        {
            return pos;
        }

        // 찾고자 하는 값이 현재 위치보다 큰 경우
        if (arr[pos] < key)
        {
            low = pos + 1;
        }
        // 찾고자 하는 값이 현재 위치보다 작은 경우
        else 
        {
            high = pos - 1;
        }
    }

    return -1; // key를 찾을 수 없는 경우
}

int main() 
{
    vector<int> arr = {10, 20, 30, 40, 50}; // 정렬된 예제 배열
    int key = 40; // 찾고자 하는 값

    // 보간 탐색 수행
    int result = interpolationSearch(arr, key);

    // 결과 출력
    if (result != -1) 
    {
        cout << "값 " << key << "을(를) 인덱스 " << result << "에서 찾았습니다." << endl;
    }
    else 
    {
        cout << "값 " << key << "을(를) 배열에서 찾을 수 없습니다." << endl;
    }

    return 0;
}

 

 

보간 탐색 장단점

 

장점 :

1. 효율성: 데이터가 균등하게 분포되어 있는 경우 매우 효율적이며, 이진 탐색보다 빠릅니다.
2. 직관적인 접근: 예상 위치를 계산하여 빠르게 접근할 수 있습니다.

단점 :

1. 균등 분포 필요: 데이터가 균등하게 분포되어 있지 않으면 성능이 저하됩니다.
2. 복잡성 증가: 위치 계산이 추가되어 구현이 이진 탐색보다 복잡합니다.

 

 

시간 복잡도

 

• 최선의 경우: O(1)O(1)O(1) (찾고자 하는 값이 예상 위치에 있는 경우)
• 평균의 경우: O(log⁡(log⁡n)) (데이터가 균등하게 분포되어 있는 경우)
• 최악의 경우: O(n) (데이터가 균등하게 분포되어 있지 않은 경우)