- 目標値
- 残りの候補
- 比較中
- 除外
- 発見
指数探索
指数探索は、整列済みのリストから2段階で値を探します。まず1, 2, 4, 8, 16番目…と位置を倍にしながら見ていき、その値が目標値より小さくなくなったら止まります。次に、最後の2つの位置の間の範囲を二分探索します。探す値を選んで、先頭に近い目標値がなぜわずかな比較で見つかるのかを確かめてください。 「再生」で探索を見るか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。破線は探す値を示し、網掛けの部分はその値がまだありうる範囲です。指数探索には整列済みのリストが必要なので、整列されていないリストは先に並べ替えます。探す値や棒の数を選ぶか、数値を自分で入力できます。ボードを選択中は、矢印キーで1ステップ移動、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。
使い方
- 探す値と棒の数を選びます。数値を自分で入力することもできます。指数探索はまずそれを並べ替えます。
- 「再生」を押すか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると、探索の好きな位置に移動できます。
- 先頭に近い値と末尾に近い値を探して、比較回数を「二分探索なら」と比べてみましょう。
指数探索のしくみ
1番目の値を見ます。目標値より小さければ2番目、さらに4, 8, 16番目と、位置を倍にしながら見ていきます。小さくない値が出たらすぐに止まります。目標値は、直前に見た位置より後ろで、この位置より前にしかありえません。その範囲を二分探索します。倍にしていってリストの末尾を越えたら、最後に見た位置から末尾までを二分探索します。
先頭に近いほど速く、長さも不要
i番目の目標値にたどり着くまでに、倍にする段階でおよそ log₂ i 回見ます。見つかる範囲の値は i 個未満なので、二分探索でさらにおよそ log₂ i 回かかります。合計でおよそ 2 log₂ i 回で、これはリストの長さではなく目標値の位置で決まります。先頭に近い目標値は普通の二分探索より速く見つかり、末尾に近い目標値は最大でおよそ2倍かかります。リストの長さをまったく使わないので、長すぎて測れないリストや終わりのわからないリストでも使えます。
よくある質問
指数探索はどのように動きますか?
整列済みのリストで1, 2, 4, 8番目…と調べ、その値が目標値より小さくなくなったら止まります。目標値は最後に調べた2つの位置の間にしかないので、その範囲を二分探索すれば見つかります。
指数探索は二分探索より速いですか?
目標値がリストの先頭に近ければ、はい。i番目の目標値なら、リストの長さに関係なく比較はおよそ 2 log₂ i 回です。目標値が末尾に近ければ普通の二分探索の方が速く、差は最大でおよそ2倍です。
何に使われますか?
ストリームや無限の数列のように、長さがわからない、または上限のないリストの探索や、次に一致する値がたいてい近くにある、整列済みのラン同士のマージに使われます。Timsort のギャロッピングモードも同じ「倍にする」考え方を使っています。
なぜ「指数」と呼ぶのですか?
調べる位置が1, 2, 4, 8, 16と、前の2倍ずつ指数的に増えるからです。倍々探索やギャロッピング探索とも呼ばれます。
入力した数値はどこかに送信されますか?
いいえ。探索はブラウザ内で実行され、最後の設定はこのブラウザのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ