N Log

보간 탐색 (Interpolation Search)

들어가는 말

이진 탐색은 탐색 범위의 중앙에 있는 값을 확인하고 범위를 절반씩 줄여 나가는 방법이었다.
보간 탐색도 이진 탐색과 마찬가지로 정렬된 데이터에 대해 수행한다.
그러나 이진 탐색과 달리 보간 탐색은 값이 전체 범위에 걸쳐 대체로 일정한 간격으로 분포한다고 가정한다.
이를 바탕으로 찾으려는 값의 예상 위치를 계산해 탐색한다.

오름차순으로 정렬된 배열에 1부터 100까지의 정수가 있고, 그중에서 값 10을 찾는다고 해보자.
이진 탐색은 먼저 중앙에 있는 값 50을 확인한 뒤 25, 12, 6, 9, 10을 차례로 확인하며 탐색 범위를 절반씩 줄인다.
반면 보간 탐색은 값 10이 전체 범위에서 앞쪽에 있다는 점을 이용해 예상 위치를 계산한다.
이 배열은 값과 인덱스가 일정한 비율로 대응하므로 보간 탐색은 첫 번째 예상 위치에서 한 번에 값 10을 찾는다.
만약 예상 위치의 값이 찾으려는 값과 다르면 비교 결과에 따라 탐색 범위를 줄이고 새로운 예상 위치를 계산한다.

비유하자면 이진 탐색은 사전에서 찾는 단어와 관계없이 항상 중간을 펼치는 방식이다.
보간 탐색은 b가 a와 z 사이에서 앞쪽에 있다는 점을 이용해 사전의 앞부분을 펼치는 방식이다.

예상 위치 계산식

예상 위치를 구하는 계산식부터 보면 각 항이 무엇을 의미하는지 이해하기 어렵다.
따라서 간단한 거리 예시에서 출발해 계산 원리를 단계적으로 살펴보자.

출발 지점이 0이고 도착 지점이 100인 직선 도로가 있다고 해보자.
현재 40 지점에 서 있다면 전체 거리의 몇 퍼센트 지점에 있는 것일까?
계산하지 않고 직감적으로 40% 지점이라는 것을 알 수 있다.

이번에는 도착 지점은 그대로 100으로 두고 출발 지점만 10으로 바꿔보자.
현재 위치 40은 전체 거리의 몇 퍼센트 지점일까?

이동 거리전체 거리=40−10100−10=3090=13=0.3‾≈33%\frac{\text{이동 거리}}{\text{전체 거리}} = \frac{40 - 10}{100 - 10} = \frac{30}{90} = \frac{1}{3} = 0.\overline{3} \approx 33\%

따라서 현재 위치 40은 출발 지점 10부터 도착 지점 100까지 전체 거리의 약 33%33\% 지점에 해당한다.

이제 예상 위치 pos를 구하는 계산식을 살펴보자.

pos=left+target−arr[left]arr[right]−arr[left]×(right−left)\begin{aligned} pos &= left + \frac{target - arr[left]}{arr[right] - arr[left]} \times (right - left) \end{aligned}

left와 right는 현재 탐색 범위의 시작 인덱스와 마지막 인덱스다.
target은 찾으려는 값이며, arr[left]와 arr[right]는 탐색 범위 양 끝에 저장된 값이다.

  1. 값 범위에서 차지하는 비율 구하기

    가운데 분수는 앞서 살펴본 도로 예시와 같은 원리다.
    분자의 target - arr[left]는 왼쪽 끝 값부터 찾으려는 값까지의 거리다.
    분모의 arr[right] - arr[left]는 왼쪽 끝 값과 오른쪽 끝 값 사이의 전체 거리다.
    두 값을 나누면 찾으려는 값이 양 끝 값 사이의 어느 지점에 있는지를 비율로 나타낼 수 있다.

  2. 비율을 인덱스 거리에 적용하기

    right - left는 현재 탐색 범위의 인덱스 거리다.
    앞에서 구한 비율에 이 거리를 곱하면 예상 위치가 left에서 인덱스로 몇 칸 떨어져 있는지 알 수 있다.

  3. 실제 예상 인덱스 구하기

    앞에서 계산한 결과는 탐색 범위의 시작 인덱스 left를 기준으로 한 상대적인 거리다.
    이 거리에 left를 더하면 실제 배열의 예상 인덱스 pos를 구할 수 있다.

  4. 실제 계산해 보기

    값이 10부터 100까지 10씩 증가하는 배열에서 target이 40인 경우를 계산해 보자.

    Value:  10  20  30  40  50  60  70  80  90  100
Index:   0   1   2   3   4   5   6   7   8    9

    배열 전체가 탐색 범위이므로 left는 0, right는 9다.
    따라서 arr[left]는 10이고 arr[right]는 100이다.

    pos=0+40−10100−10×(9−0)=0+3090×9=0+13×9=0+3=3\begin{aligned} pos &= 0 + \frac{40 - 10}{100 - 10} \times (9 - 0) \\ &= 0 + \frac{30}{90} \times 9 \\ &= 0 + \frac{1}{3} \times 9 \\ &= 0 + 3 \\ &= 3 \end{aligned}

    계산된 예상 인덱스는 3이며, arr[3]의 값이 40이므로 한 번에 target을 찾는다.

탐색 과정 살펴보기

탐색에 성공하는 경우

오름차순으로 정렬된 다음 배열에서 값 6의 인덱스를 찾아보자.

Value:  1  2  3  4  5  6  7
Index:  0  1  2  3  4  5  6

처음에는 배열 전체가 탐색 범위이므로 left는 시작 인덱스 0, right는 마지막 인덱스 6으로 정한다.
위치 계산식에 값을 대입하면 pos = 0 + (6 - 1) × (6 - 0) / (7 - 1) = 5가 된다.
arr[5]의 값이 6으로 찾으려는 값과 같으므로 인덱스 5를 반환한다.

회차 left right pos arr[pos] 비교 처리
1 0 6 5 6 6 == 6 인덱스 5를 반환

탐색에 실패하는 경우

같은 배열에서 존재하지 않는 값 8의 인덱스를 찾아보자.

보간 탐색은 예상 위치를 계산하기 전에 target이 현재 탐색 범위의 최솟값과 최댓값 사이에 있는지 확인해야 한다.
이 확인 없이 위치를 계산하면 유효하지 않은 배열 인덱스에 접근할 수 있다.

값의 범위를 검사하지 않고 target이 8일 때의 위치를 계산해 보자.
pos = 0 + (8 - 1) × (6 - 0) / (7 - 1) = 7이 되어 배열의 마지막 인덱스인 right보다 큰 값이 계산된다.

값이 균등하게 분포되지 않은 경우

이번에는 마지막 원소만 다른 값과 큰 차이가 나는 배열에서 값 6의 인덱스를 찾아보자.

Value:  1  2  3  4  5  6  100
Index:  0  1  2  3  4  5    6

1회차의 예상 위치는 pos = 0 + (6 - 1) × (6 - 0) / (100 - 1) = 0이다.
배열의 마지막 값 100 때문에 값의 범위가 커져 찾으려는 값 6의 상대적인 위치가 실제보다 왼쪽에 가깝게 계산된다.
정수로 변환하는 과정에서 소수점 이하를 버리므로 pos는 left와 같은 위치가 된다.

회차 left right pos arr[pos] 비교 처리
1 0 6 0 1 1 < 6 left를 pos + 1인 1로 변경
2 1 6 1 2 2 < 6 left를 pos + 1인 2로 변경
3 2 6 2 3 3 < 6 left를 pos + 1인 3으로 변경
4 3 6 3 4 4 < 6 left를 pos + 1인 4로 변경
5 4 6 4 5 5 < 6 left를 pos + 1인 5로 변경
6 5 6 5 6 6 == 6 인덱스 5를 반환

예상 위치가 매번 탐색 범위의 왼쪽 끝으로 계산되어 탐색 범위가 한 칸씩만 줄어든다.
이처럼 값이 균등하게 분포되지 않으면 보간 탐색도 선형 탐색처럼 최대 n개의 원소를 확인할 수 있다.

시간 복잡도

데이터가 균등하게 분포되어 있으면 예상 위치가 실제 위치에 가까워 평균 시간 복잡도는 O(log⁡(log⁡n))O(\log(\log n))이다.
그러나 데이터가 한쪽에 몰려 있으면 탐색 범위가 조금씩만 줄어들 수 있으므로 최악의 시간 복잡도는 O(n)O(n)이다.

nn log⁡2n\log_2 n log⁡2(log⁡2n)\log_2(\log_2 n)
십만 16.61 4.05
백만 19.93 4.32
천만 23.25 4.54
억 26.58 4.73

소스 코드

#include <stdio.h>

int interpolation_search(const int arr[], int size, int target)
{
    int left = 0;
    int right = size - 1;

    while (1)
    {
        if (left > right)
            return -1;

        if (target < arr[left] || target > arr[right])
            return -1;

        if (arr[left] == arr[right])
            return left;

        int pos = left +
                  (int)(((double)target - arr[left]) /
                        ((double)arr[right] - arr[left]) *
                        (right - left));

        if (arr[pos] == target)
            return pos;

        if (arr[pos] < target)
            left = pos + 1;
        else
            right = pos - 1;
    }
}

int main(void)
{
    int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 6;
    int index = interpolation_search(arr, size, target);

    if (index != -1)
        printf("%d is at index %d.\n", target, index);
    else
        printf("%d was not found.\n", target);

    return 0;
}

구현 설명

이진 탐색의 코드와 비교하면 비슷한 부분이 많다.
pos를 구하는 방법은 이 글의 앞부분 예상 위치 계산식에서 살펴보았으므로 여기서는 설명을 생략한다.

이진 탐색에서는 while(left <= right)만으로 반복 여부를 결정할 수 있었다.
반면 보간 탐색에서는 몇 가지 조건을 추가로 확인해야 한다.
이 조건들을 while문에 모두 나열하면 가독성이 떨어진다고 판단해 각각 별도의 if문으로 나누었다.

  1. 탐색 범위 확인

    if (left > right)
    return -1;

    left > right는 이진 탐색의 반복 조건인 left <= right를 반대로 검사한 것이다.
    left가 right보다 크면 유효한 탐색 범위가 남아 있지 않으므로 -1을 반환한다.

  2. 값 범위 확인

    if (target < arr[left] || target > arr[right])
    return -1;

    오름차순으로 정렬된 배열에서 arr[left]는 현재 탐색 범위의 최솟값이고 arr[right]는 최댓값이다.
    따라서 target이 두 값 사이에 없다면 현재 탐색 범위에 존재할 수 없다.

    이진 탐색에서는 이러한 값 범위 확인 코드를 보지 못했을 것이다.
    이진 탐색의 mid는 target 값과 관계없이 항상 left와 right 사이에서 계산되므로, 배열 범위를 벗어난 인덱스에 접근할 위험이 없다.

    반면 보간 탐색에서는 예상 위치를 계산하기 전에 이 조건을 반드시 확인해야 한다.
    target이 양 끝 값의 범위를 벗어나면 계산된 pos도 left와 right 사이를 벗어나 유효하지 않은 배열 인덱스를 참조할 수 있기 때문이다.

  3. 양 끝 값이 같은 경우 처리

    if (arr[left] == arr[right])
    return left;

    예상 위치 계산식의 분모인 arr[right] - arr[left]가 0이면 0으로 나누게 되므로 별도 처리가 필요하다.
    이때 -1을 반환하지 않고 left를 반환하는 이유는 양 끝 값이 같아도 찾으려는 값이 존재할 수 있기 때문이다.
    분모가 0이 되는 경우는 양 끝 값이 모두 0일 때뿐만이 아니라, 두 값이 같을 때도 그렇다.
    예를 들어 arr[left]와 arr[right]가 모두 5여도 5 - 5는 0이 된다.
    그래서 조건식에서 두 값이 같은지 확인한다.

    이 코드에 도달했다면 2번 값 범위 확인을 이미 통과했으므로, target은 arr[left] 이상 arr[right] 이하이다.
    오름차순으로 정렬된 배열에서 양 끝 값이 같다면 그 사이의 모든 원소도 같은 값이므로, target도 그 값과 같을 수밖에 없다.
    따라서 left와 right 중 어느 인덱스를 반환해도 된다.