補間探索

補間探索は、現在の範囲の両端にある値と目標値を比べ、目標値がどの位置にあるかを推定します。昇順に並んだデータの値がほぼ均等に分布していれば、値を使って位置を推定するため、常に中央を調べる二分探索より少ない探索回数で目標値に到達できることがあります。値が一部に集中していたり、間隔が不均一だったりすると推定の効果は下がるため、値の分布が重要です。辞書で「さ」から始まる単語を探すとき、中央ではなく後ろ寄りのページを開き、見つけた内容に応じて範囲を絞る様子にたとえられます。

補間探索アルゴリズム

昇順の配列 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 と一致すれば端のインデックスを返し、一致しなければその範囲に目標値はありません。境界が交差したら探索を終了します。また、目標値が現在の両端の値の範囲外なら、すぐに除外できます。これらの確認により、ゼロ除算と空の範囲へのインデックス参照を防げます。

補間探索の例

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) です。別の配列を確保せず、再帰も使いません。