- 目標値
- 残りの候補
- 比較中
- 除外
- 発見
補間探索
補間探索は、電話帳を開くように整列済みのリストから値を探します。「渡辺」さんを探すなら、真ん中ではなく後ろのほうを開きますよね。残りの部分の両端の値から、目標値の位置を推定します。探す値と値の分布を選び、探査を1回ずつ進めて、推定が二分探索に勝つときと負けるときを確かめましょう。 「再生」で探索を見るか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。破線は探す値を示し、網掛けの部分はその値がまだありうる範囲です。補間探索には整列済みのリストが必要なので、整列されていないリストは先に整列します。探す値、値の分布、棒の数を選ぶか、数値を自分で入力できます。ボードを選択中は、矢印キーで1ステップ移動、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。
使い方
- 探す値、値の分布、棒の数を選びます。数値を自分で入力することもできます。補間探索はまずそれを整列します。
- 「再生」を押すか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると、探索の好きな位置に移動できます。
- 「分布」を「均等」「ランダムな間隔」「偏り」で切り替えて、「探査」と「二分探索なら」を比べてみましょう。
補間探索のしくみ
整列済みリストのうち、目標値がまだありうる部分の最初と最後の値を見ます。目標値が、たとえば最初の値から最後の値までの 40% のところにあれば、その部分の 40% の位置を探査します。そこの値が目標値なら完了です。小さければその後ろの位置だけが残り、大きければその前の位置だけが残ります。残りの部分でもう一度推定します。目標値が最初の値より小さいか、最後の値より大きければ、リストにはありません。
推定がうまくいくとき
10, 20, 30 のように値が均等に分布していれば、最初の推定で目標値かそのすぐ近くに当たり、平均で約 log₂(log₂ n) 回の探査で済みます。10億個の値でも約 5 回で、二分探索なら 30 回です。1, 2, 3, 4, 1000 のように値が偏っていると、推定は何度も見当違いの位置に当たり、1回の探査で1つの値しか除けないこともあるので、最悪の場合は n 回の探査が必要です。二分探索は約 log₂ n 回より悪くなることはありません。
よくある質問
補間探索はどのように動きますか?
整列済みのリストで、残りの部分の最初と最後の値から目標値の位置を推定し、その位置を探査して、正しい側の部分だけを残します。真ん中よりも賢い推測をする二分探索のようなものです。
補間探索は二分探索より速いですか?
値が均等に分布していれば速いです。平均で約 log₂ n 回ではなく約 log₂(log₂ n) 回の探査で済みます。分布が偏っていると大幅に遅くなることがあり、最大で n 回の探査が必要ですが、二分探索は約 log₂ n 回を超えることはありません。
なぜ遅くなることがあるのですか?
推定が、値が均等に増えていくことを前提にしているからです。ほとんどの値が小さく一部だけが非常に大きいと、小さい目標値の推定は何度も先頭近くに当たり、1回に1つか2つの値しか除けません。
補間探索はどこで使われますか?
キーがほぼ均等に分布していて、探査のコストが高い場面です。たとえば、ディスク上のレコードを数値 ID やハッシュで探すときです。多くのシステムでは二分探索と組み合わせて、最悪の場合の性能を保ちます。
入力した数値はどこかに送信されますか?
いいえ。探索はブラウザ内で実行され、最後の設定はこのブラウザのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ