補間探索（Interpolation Search）アルゴリズムをC++で実装する方法

補間探索とは

二分探索では、リストを毎回等しい大きさの部分に分割しながら探索ら探索範囲を絞り込んでいきます。一方、補間探索では補間公式を使い、キーが存在すると推定されるおおよその位置を直接計算で求めます。推定位置が判明したら、その位置を基準にリストを分割して探索を進めます。毎回キーの正確な位置に近づこうとするため、探索にかかる時間を大幅に短縮できます。

この手法は、データがソート済みであり、かつ値ができるだけ一様に分布している場合に特に高い効果を発揮します。

キーの推定位置は次の式で求められます。

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

これは、キーの値が配列全体の値の範囲の中でどの割合の位置にあるかを線形補間によって予測するものです。

補間探索の計算量

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

• 空間計算量：O(1)

入出力例

入力 − ソート済みのデータリスト
10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995
検索キー：780

出力 − 要素が見つかりました。位置：16

アルゴリズム

interpolationSearch(array, start, end, key)

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

出力：キーが見つかった場合はその位置、見つからない場合は無効な位置（-1）

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

処理の流れを整理すると、次の手順になります。

1. キーが現在の探索範囲 [start, end] の中に収まっているか確認する。収まっていなければ、キーは存在しない。
2. 補間公式からキーの推定位置 estimate を計算する。
3. array[estimate] がキーと一致すれば、その位置を返す。
4. array[estimate] がキーより小さければ探索範囲の下限を estimate+1 に、大きければ上限を estimate-1 に更新して繰り返す。

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 << "要素数を入力してください: ";
    cin >> n;
    int arr[n];                                        // サイズnの配列を作成
    cout << "要素を入力してください: " << endl;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "検索するキーを入力してください: ";
    cin >> searchKey;
    if((loc = interpolationSearch(arr, 0, n-1, searchKey)) >= 0)
        cout << "要素が見つかりました。位置: " << loc << endl;
    else
        cout << "要素はリスト内に見つかりませんでした。" << endl;
}

実行結果

要素数を入力してください: 20
要素を入力してください:
10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995
検索するキーを入力してください: 780
要素が見つかりました。位置: 16

まとめ

補間探索は、データが一様に分布したソート済みリストに対して非常に高速に動作する探索アルゴリズムです。二分探索のように機械的に範囲を半分にするのではなく、値の分布から位置を推定することで、平均 O(log log n) という優れた時間計算量を実現します。ただし、分布が極端に偏っている場合は最悪 O(n) まで性能が落ちるため、適用するデータの性質を見極めることが重要です。