보간 검색

보간 검색은 현재 범위 양 끝의 값과 목표값을 비교해 목표가 있을 위치를 추정합니다. 값이 대체로 고르게 분포된 정렬 데이터에서는 항상 중간을 확인하는 이진 검색보다 적은 탐색 횟수로 목표를 찾을 수 있습니다. 값이 특정 구간에 몰려 있거나 간격이 불규칙하면 추정의 효용이 떨어지므로 데이터 분포에 관한 가정이 중요합니다. 사전에서 ‘s’로 시작하는 단어를 찾을 때 가운데보다 뒤쪽을 먼저 펼친 다음, 확인한 내용에 따라 페이지 범위를 좁히는 비유가 유용합니다. 이 비유는 보간 검색이 값에 따라 다음 위치를 추정하는 방식을 보여 줍니다. (이진 검색)

보간 검색 알고리즘

오름차순 배열 A에서 목표값 X를 찾을 때는 처음과 마지막 인덱스를 포함하는 경계 lo와 hi를 유지합니다. 배열은 정렬되어 있어야 합니다. 그렇지 않으면 범위 비교와 탐색 위치 추정만으로 값을 안전하게 제외할 수 없습니다. X가 A[lo]와 A[hi] 사이에 있는 동안 다음 식으로 위치를 추정합니다.

mid = lo + (X - A[lo]) * (hi - lo) / (A[hi] - A[lo])

계산에 정수 나눗셈을 사용하므로 추정값은 배열 인덱스가 됩니다. A[mid]가 X보다 작으면 mid + 1부터 계속하고, 크면 mid - 1부터 계속합니다. 값이 같으면 mid를 반환합니다. 위치를 추정하기 전에 양 끝 값이 같은 경우를 처리해야 합니다. 그 값이 X와 같으면 끝 인덱스를 반환하고, 다르면 해당 범위에 목표값이 없습니다. 경계가 서로 교차하면 탐색을 멈춥니다. 현재 양 끝 값의 범위 밖에 있는 목표값도 바로 제외할 수 있습니다. 이런 검사는 0으로 나누는 일을 막고 빈 범위를 인덱싱하지 않도록 합니다.

보간 검색 예제

A = (1, 3, 7, 8, 11, 15, 17, 18, 21)에서 목표값 X = 18을 찾는다고 가정해 보겠습니다. 처음에는 lo = 0, hi = 8, A[lo] = 1, A[hi] = 21입니다. 정수 나눗셈을 적용한 위치 추정값은 0 + (18 - 1) * (8 - 0) / (21 - 1) = 6입니다. A[6] = 17은 목표값보다 작으므로 lo = 7로 바꿉니다. 다음 추정값은 7 + (18 - 18) * (8 - 7) / (21 - 18) = 7입니다. 이제 A[7] = 18이므로 검색 결과로 인덱스 7을 반환합니다.

보간 검색 알고리즘 구현

다음 C++ 예제는 추적 예제와 같은 값과 목표값을 사용합니다. 목표값을 찾으면 0부터 시작하는 인덱스를 반환하고, 찾지 못하면 -1을 반환합니다.

예제를 실행해 보세요.

이 섹션의 코드와 표시되는 레이블 또는 출력은 영어로 유지됩니다.

#include <iostream>
#include <limits>
#include <vector>

static_assert(std::numeric_limits<int>::digits <= 31,
              "This implementation supports int types up to 32 bits");

int interpolationSearch(const std::vector<int>& values, int target) {
    if (values.empty() ||
        values.size() > static_cast<std::size_t>(std::numeric_limits<int>::max())) {
        return -1;
    }

    int lo = 0;
    int hi = static_cast<int>(values.size()) - 1;
    while (lo <= hi && target >= values[lo] && target <= values[hi]) {
        if (values[lo] == values[hi]) {
            return values[lo] == target ? lo : -1;
        }

        const int mid = lo + static_cast<int>(
            ((static_cast<long long>(target) - static_cast<long long>(values[lo])) *
             (hi - lo)) /
            (static_cast<long long>(values[hi]) -
             static_cast<long long>(values[lo])));

        if (values[mid] == target) return mid;
        if (values[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

int main() {
    const std::vector<int> values{1, 3, 7, 8, 11, 15, 17, 18, 21};
    const int target = 18;
    const int result = interpolationSearch(values, target);
    if (result >= 0) std::cout << "Element found at index " << result << '\n';
    else std::cout << "Element not found\n";
}

Element found at index 7

가드는 원소가 0개인 벡터, 현재 값의 범위를 벗어난 목표값, 양 끝 값이 같은 범위를 처리합니다. 이 구현은 int가 최대 32비트이고 벡터 원소 수가 INT_MAX 이하라고 가정하며, 인덱스를 int로 변환하기 전에 크기를 확인합니다. 뺄셈을 하기 전에 두 값을 모두 long long으로 변환하면 전체 32비트 int 범위에서 분자 차와 분모가 안전하게 계산됩니다. 가능한 가장 큰 분자 곱은 (2^32 - 1) * (INT_MAX - 1)이며, 부호 있는 64비트 long long에 들어갑니다. 몫은 0부터 hi - lo 사이이므로 이를 lo에 더해도 경계 안에 머뭅니다. 입력 배열은 여전히 오름차순으로 정렬되어 있어야 합니다. 예제는 독립적으로 완결되어 있으며 추가 파일이 필요하지 않습니다. 코드와 출력에 표시되는 문구는 바이트 단위로 보존되므로 영어로 표시됩니다.

보간 검색 알고리즘의 복잡도

시간 복잡도

최선의 경우는 O(1)입니다. 첫 번째로 추정한 위치에 목표값이 있습니다. 정렬된 범위에서 값이 대략 균일하게 분포하면 평균 시간은 O(log log n)입니다. 값에 따라 위치를 추정할 때마다 구간이 훨씬 작아지는 경향이 있기 때문입니다. 이 평균 시간은 분포 가정에 달려 있으며, 모든 정렬 배열에서 보장되는 결과는 아닙니다.

최악의 경우는 O(n)입니다. 값에 따른 추정으로 탐색 범위가 계속 조금씩만 줄어들면 선형 개수의 위치를 확인할 수 있습니다. 분포가 매우 불균일할 때 이런 일이 생길 수 있습니다. 따라서 분포를 알 수 없거나 불규칙하다면 이진 검색의 성능이 더 예측 가능할 수 있습니다.

공간 복잡도

반복 방식 구현은 고정된 수의 스칼라 변수를 사용하므로 보조 공간은 O(1)입니다. 별도의 배열을 할당하거나 재귀 호출을 하지 않습니다.