はじめに 長さ$n$の昇順にソートされた配列から指定したkeyが格納された位置$i$（もしそのkeyがなければ、その値が格納されるべき位置）を返す問題を考えます。 よく知られた二分探索を使えば、$O(\log n)$時間で解くことが出来ますが、指数探索（exponential search）を使えばより高速に、$O(\log i)$時間で解くことが出来ます（正確に言うと$i$は高々$n$なので指数探索は二分探索よりも同等あるいは高速に動作します）。 オーダー表記では定数項を無視しているので実際には二分探索の方が速い場面も多いですが、特殊なケース、例えばクエリに偏りがあり、配列の前方ばかりを返すような場合には二分探索よりも高速に動作します。 指数探索アルゴリズム アルゴリズムは２つのフェーズに分かれます。 第一フェーズ 第一フェーズでは、keyが格納されている範囲を特定します。 ここでは配列