補間探索は、高速で効率的な探索アルゴリズムです。これは、配列要素がソートされた配列に一様に分散しているシナリオのための二分探索アルゴリズムを改善します。これは、要求された値のプロービング位置で動作します。二分探索とは異なり、常に配列の中央に行くわけではなく、探索すべきキーの値に応じて任意の位置に行くことができる。推定位置での値を比較し、その前後の部分に探索空間を縮小していきます。例えば、辞書で単語を探索する際には、探索空間を毎回半分に分割するのではなく、その中の文字の位置に応じてページをめくるようにしています。 補間探索アルゴリズム ここで、n の要素を含むソートされていない配列 A[] があり、与えられた要素 X を見つけたいとします。 lo を 0、mid を -1、hi を n-1 とする。 lo <= hi とし、X が lo と hi の間の範囲にあるとき、すなわち X >= A[lo] と X <= A[hi] とする。 プローブ位置の式 - mid = lo + (X - A[lo]) * (hi - lo) / (A[hi] - A[lo]) を用いて mid を計算します。 プローブ位置の要素がターゲットの要素よりも小さい場合は、右に移動します。A[mid] < X の場合、lo を mid + 1 とします。 そうでない場合は左に移動します。A[mid] > X の場合は、hi を mid-1 とします。 そうでなければ要素が見つかったので mid を返します。 lo == hi , 残りの要素が一つだけの場合、それが対象の要素かどうか、つまり A[lo]==X であるかどうかをチェックします。 つまり、A[lo]== X ならば、A[lo] を返します。 そうでなければ -1 を返します。 補間探索の例 配列 (1, 3, 7, 8, 11, 15, 17, 18, 21) があり、X - 18 を求めたいとします。