補間探索

電話帳で「渡辺」さんを探すとき、真ん中からは開きません。「わ」は五十音の最後のほうなので、後ろのほうを開きます。補間探索は数値で同じことをします。目標値の大きさからその位置を推測し、均等に分布したデータでは、その推測が驚くほどよく当たります。

整列された棒の列と、最初の棒から最後の棒へ引いた線。目標値の高さがその線と交わる位置に探査が置かれている
整列された棒の列と、最初の棒から最後の棒へ引いた線。目標値の高さがその線と交わる位置に探査が置かれている

考え方

二分探索は、何を探していても常に真ん中を探査します。補間探索は値を利用します。残りの部分が 10 から 100 までで目標値が 70 なら、目標値は最初の値から最後の値までの 3 分の 2 のところにあるので、その部分の 3 分の 2 の位置を探査します。式で書くと、探査位置は lo + (target − a[lo]) / (a[hi] − a[lo]) × (hi − lo) です。探査の後は、二分探索とまったく同じように正しい側の部分を残し、もう一度推定します。

2つの例

10, 20, 30, 40, 50, 60, 70, 80, 90, 100 で 70 を探すと、いきなり 7 番目を探査します。1 回の探査で見つかり、二分探索なら 4 回かかります。次に 1, 2, 3, 4, 5, 6, 7, 8, 9, 999 で 9 を探します。999 があるせいで推定は毎回先頭近くに当たり、1 番目、2 番目、3 番目…と1つずつ探査して、9 回の探査が必要です。二分探索なら 3 回です。

どれくらい速いか

値が均等に分布しているか、一様分布から無作為に選ばれている場合、1 回の探査で残りの部分は約 n から約 √n に縮みます。そのため平均で約 log₂(log₂ n) 回の探査で済みます。10億個の値でも約 5 回で、二分探索なら 30 回です。値の分布が大きく偏っていると、1 回の探査で 1 つの値しか除けないこともあり、最悪の場合は線形探索と同じく n 回の探査になります。探査のたびに割り算も必要なので、実際に得をするのは主に、ディスクからの読み込みのように探査のコストが高い場合です。

歴史と変種

W. W. Peterson は 1957 年、ランダムアクセス記憶装置上のレコードを探すために補間探索を発表しました。キーが均等に分布しているときの平均 log log n は、1978 年に Perl、Itai、Avni が証明しました。実用的な版では、二分探索のステップを混ぜて悪いデータに備えます。たとえば補間逐次探索や補間二分探索で、最悪の場合も log n に近く保てます。

試してみよう

アプリを開き、「探す値」で値を選んで「ステップ」を押します。各探査で、目標値が両端の値の間のどのあたりにあり、それが何番目を指すかが表示されます。「分布」を「均等」にするとほとんどの探索が 1 回の探査で終わり、「偏り」にすると探査がリストの先頭をじりじり進みます。最後のタイルには、同じ値で二分探索なら何ステップ必要かが表示されます。

よくある質問

補間探索の時間計算量は?

値が均等に分布していれば平均 O(log log n)、最悪の場合は O(n) です。追加メモリは O(1) で、整列済みのリストが必要です。

補間探索と二分探索の違いは?

二分探索は常に残りの部分の真ん中を探査します。補間探索は両端の値から判断して、目標値がありそうな位置を探査します。均等に分布した値ではずっと有利ですが、偏った値ではずっと不利になることがあります。

補間探索に向いているのはどんなデータ?

ほぼ均等に分布した整列済みの数値キーです。欠番の少ない連番 ID、定期的なイベントのタイムスタンプ、ハッシュ化したキーなどです。探査のコストが高く、ちょっとした計算は安いデータに向いています。

アプリで分布を選べるのはなぜ?

分布によって推定の精度が決まるからです。均等な値では補間探索がまるで魔法のように見え、偏った値ではその弱点がわかります。二分探索の回数と比べるのが、どちらをいつ使うべきかを知るいちばんわかりやすい方法です。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

補間探索を試す