補間探索とは？仕組み・計算量・C++実装コードをわかりやすく解説

二分探索では、リストを常に等しい部分に分割しながら探索範囲を絞り込んでいきます。一方、補間探索（Interpolation Search）では、補間公式を用いて「キーが存在するであろう正確な位置」を直接推定しようとします。推定位置が求まったら、その位置を基準にリストを分割して探索を続行します。

毎回キーの正確な位置を見つけようとするため、探索にかかる時間を大幅に短縮できます。この手法は、データが一様に分布している場合に特に高い性能を発揮し、効率よく目的の要素を見つけ出すことができます。

補間探索の計算量

• 時間計算量： 平均ケースで O(log₂(log₂ n))、最悪ケースで O(n)（データが指数関数的に分布している場合）
• 空間計算量： O(1)

平均ケースにおける O(log log n) という極めて高速な動作は、二分探索の O(log n) をさらに上回ります。ただし、データの偏りが大きい場合は最悪ケースで線形時間まで劣化する点に注意が必要です。

入力と出力

Input:
A sorted list of data:
10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995
The search key 780
Output:
Item found at location: 16

アルゴリズム

interpolationSearch(array, start, end, key)

入力： ソート済みの配列、探索範囲の開始位置と終了位置、探索キー

出力： キーが見つかった場合はその位置、見つからない場合は不正な位置

Begin
    while start <= end AND key >= array[start] AND key <= array[end] do
        dist := key – array[start]
        valRange := array[end] – array[start]
        fraction := dist / valRange
        indexRange := end – start
        estimate := start + (fraction * indexRange)
        if array[estimate] = key then
            return estimate position
        if array[estimate] < key then
            start := estimate + 1
        else
            end = estimate -1
    done
    return invalid position
End

アルゴリズムのポイント

この擬似コードの核となるのは、次の補間公式です。

estimate = start + ((key - array[start]) / (array[end] - array[start])) × (end - start)

キーの値が配列の値域の中でどのあたりに位置するかを比率として求め、それをインデックスの範囲に対応させることで、候補位置を一発で見積もります。その後、推定位置の値とキーを比較し、見つかれば位置を返し、見つからなければ探索範囲を絞って繰り返します。

C++による実装例

#include<iostream>
using namespace std;
int interpolationSearch(int array[], int start, int end, int key) {
    int dist, valRange, indexRange, estimate;
    float fraction;

    while(start <= end && key >= array[start] && key <= array[end]) {
        dist = key - array[start];
        valRange = array[end] - array[start]; // 値の範囲
        fraction = dist / valRange;
        indexRange = end - start;
        estimate = start + (fraction * indexRange); // キーの推定位置

        if(array[estimate] == key)
            return estimate;
        if(array[estimate] < key)
            start = estimate +1;
        else
            end = estimate - 1;
    }
    return -1;
}

int main() {
    int n, searchKey, loc;
    cout << "Enter number of items: ";
    cin >> n;
    int arr[n]; // サイズ n の配列を作成
    cout << "Enter items: " << endl;

    for(int i = 0; i< n; i++) {
        cin >> arr[i];
    }

    cout << "Enter search key to search in the list: ";
    cin >> searchKey;

    if((loc = interpolationSearch(arr, 0, n-1, searchKey)) >= 0)
        cout << "Item found at location: " << loc << endl;
    else
        cout << "Item is not found in the list." << endl;
}

実行結果

Enter number of items: 20
Enter items:
10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995
Enter search key to search in the list: 780
Item found at location: 16

まとめ

補間探索は、データがソート済みかつ一様に分布している場合に威力を発揮する探索アルゴリズムです。平均 O(log log n) という非常に高速な探索が可能である一方、分布が偏っている場合は性能が落ちるため、適用する場面の選択が重要になります。数値データのように値の分布が予測しやすいケースで、ぜひ活用してみてください。