指数探索

二分探索は、中央を見る前にリストがどこで終わるかを知る必要があります。指数探索はその必要がありません。目標値を越えるまでどんどん大きな歩幅で前へ駆け進み、最後の1歩の範囲を二分探索します。そのため長さのわからないリストにうってつけで、先頭に近い値もすばやく見つかります。

整列した棒の列。長さが倍になっていくジャンプで1, 2, 4, 8番目を進み、最後の2つのジャンプの間の範囲が網掛けになっている
整列した棒の列。長さが倍になっていくジャンプで1, 2, 4, 8番目を進み、最後の2つのジャンプの間の範囲が網掛けになっている

考え方

1番目の値を調べ、次に2, 4, 8, 16番目…と、前の位置の2倍ずつ調べます。その値が目標値より小さい間は、目標値はもっと先にあるはずです。初めて小さくない値に出会ったら、目標値は追い詰められています。直前に調べた位置より後ろで、この位置以前にあります。その範囲は整列済みなので、二分探索で目標値が見つかるか、ないことがわかります。

例

2, 5, 8, 12, 16, 23, 38, 56, 72, 91 から23を探します。1番目は2、2番目は5、4番目は12で、どれも小さい値です。8番目は56で大きいので、23は5〜7番目にしかありえません。二分探索でその中央の6番目を調べると23が見つかります。比較は5回で、普通の二分探索なら3回です。同じリストで12を探すと、3回の比較で4番目で止まり、二分探索より1回少なく済みます。2は1番目にあり、比較1回で見つかります。

比較回数

i番目の目標値なら、倍にする段階はおよそ log₂ i 歩で止まり、残る範囲は i 個未満の位置なので、二分探索でさらにおよそ log₂ i 回かかります。つまりリストの長さに関係なく、比較はおよそ 2 log₂ i 回です。目標値が先頭に近ければ、常におよそ log₂ n 回かかる二分探索より有利です。末尾に近ければ、指数探索は最大でおよそ2倍かかります。値が40個の場合、このアプリでは最初の5つの位置で平均およそ3回、最後の5つでおよそ9回の比較になり、二分探索はおよそ4.6回です。

長さが不明な場合とギャロッピング

Jon Bentley と Andrew Yao は1976年に、この倍にしていく方法を非有界探索のために示しました。無限のリストや、位置を指定して調べることしかできないストリームのように、終わりのわからない整列済みの列から値を探す問題です。同じ考え方はマージの高速化にも使えます。2つの整列済みのランの一方が勝ち続けると、Timsort はギャロッピングに切り替えます。次の値が入る場所を探すために、もう一方のランで1つずつ進むのではなく、1, 2, 4, 8個先を見ていきます。

試してみよう

アプリを開き、「探す値」で値を選んで「ステップ」を押します。1, 2, 4, 8番目…を見るたびに強調表示され、小さくない値が出ると最後の2つの位置の間の範囲が網掛けになり、二分探索に切り替わります。小さい値と大きい値を探して、比較回数を二分探索のタイルと比べてみましょう。

よくある質問

指数探索の時間計算量は?

i番目の目標値なら O(log i) なので、値が n 個のリストでも最大 O(log n) です。追加のメモリは O(1) で、整列済みのリストが必要です。

指数探索と二分探索の違いは?

二分探索はリスト全体から始め、その長さを必要とします。指数探索はまず倍にしていくことで目標値を含む範囲を見つけ、その範囲だけを二分探索します。目標値が先頭に近いほど速く、長さを知らなくても使えます。

なぜ一定の幅を足すのではなく、歩幅を倍にするのですか?

一定の幅を足すのはジャンプ探索で、リストを渡りきるのにおよそ n を幅で割った回数だけ見る必要があります。倍にすればおよそ log₂ i 回で i番目に届き、残る範囲も必要な大きさの2倍を超えないので、その後の二分探索も短く済みます。

指数探索はどこで使われますか?

上限のない、またはとても長い整列済みデータの探索、整列済みのランのマージ(Timsort のギャロッピング)、そして上限がわからないときに条件が初めて真になる位置を探す場合です。

試してみますか?

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

指数探索を試す