JavaScriptで学ぶ補間探索（Interpolation Search）の基本と実装方法

補間探索（Interpolation Search）とは

補間探索は、キーに割り当てられた数値（キー値）によって昇順にソートされた配列の中から、特定のキーを効率的に見つけ出すための検索アルゴリズムです。

二分探索が常に範囲の中央を確認するのに対し、補間探索は「値の分布」を考慮して、ターゲットが存在しそうな位置を予測してアクセスする点が大きな特徴です。データが一様に分布している場合、平均時間計算量はO(log log n)と非常に高速に動作します。

具体的な例

例えば、一様に分布したn個の値を持つソート済み配列arr[]があるとします。この中から特定の要素targetを検索する関数を作成するケースを考えてみましょう。

補間探索では、目的の位置を見つけるために次の式を使って推定位置posを計算します。

pos = lo + ((x - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]))

// この式の考え方は、検索対象の要素がarr[hi]に近いほどposの値を大きく、
// arr[lo]に近いほど小さくなるように位置を推定するというものです。

式で使われる各要素の意味

• arr[] — 検索対象の要素が格納された配列
• x — 探したい要素（検索値）
• lo — 配列arr[]の検索範囲の開始インデックス
• hi — 配列arr[]の検索範囲の終了インデックス

JavaScriptでの実装

それでは、第一引数に数値の配列、第二引数に検索ターゲットを受け取り、補間探索アルゴリズムを使ってターゲットのインデックスを返すJavaScript関数を実装してみましょう。要素が見つからない場合は-1を返します。

サンプルコード

const arr = [1, 4, 6, 7, 9, 12, 15, 16, 17, 23, 25, 26, 27, 31];
const target = 25;

const interpolationSearch = (arr = [], target) => {
    let left = 0;
    let right = arr.length - 1;
    while (left <= right) {
        const rangeDelta = arr[right] - arr[left];
        const indexDelta = right - left;
        const valueDelta = target - arr[left];
        if (valueDelta < 0) {
            return -1;
        }
        if (!rangeDelta) {
            return arr[left] === target ? left : -1;
        }
        const middleIndex = left + Math.floor((valueDelta * indexDelta) / rangeDelta);
        if (arr[middleIndex] === target) {
            return middleIndex;
        }
        if (arr[middleIndex] < target) {
            left = middleIndex + 1;
        } else {
            right = middleIndex - 1;
        }
    };
    return -1;
};

console.log(interpolationSearch(arr, target));

実行結果

上記のコードをコンソールで実行すると、次の出力が得られます。

10

ターゲットの25は配列のインデックス10の位置に存在するため、正しく10が返されています。

計算量の目安

• 平均計算量：O(log log n) — データが一様に分布している場合
• 最悪計算量：O(n) — データの偏りが大きい場合

このように、補間探索はソート済みかつ一様な分布を持つデータに対して特に威力を発揮するアルゴリズムです。条件に合う場面では二分探索よりも高速に動作するため、ぜひ活用してみてください。