はじめに
長さ$n$の昇順にソートされた配列から指定したkeyが格納された位置$i$（もしそのkeyがなければ、その値が格納されるべき位置）を返す問題を考えます。
よく知られた二分探索を使えば、$O(\log n)$時間で解くことが出来ますが、指数探索（exponential search）を使えばより高速に、$O(\log i)$時間で解くことが出来ます（正確に言うと$i$は高々$n$なので指数探索は二分探索よりも同等あるいは高速に動作します）。
オーダー表記では定数項を無視しているので実際には二分探索の方が速い場面も多いですが、特殊なケース、例えばクエリに偏りがあり、配列の前方ばかりを返すような場合には二分探索よりも高速に動作します。
指数探索アルゴリズム
アルゴリズムは２つのフェーズに分かれます。
第一フェーズ
第一フェーズでは、keyが格納されている範囲を特定します。
ここでは配列の要素は昇順に並んでおり、keyは配列の中に存在するものとして説明します（存在しなくても動作手順は同じです）。
$j=0$を初期値とし、$2^j$番目の値がkeyより小さいか否かを比較します、もし小さければ、keyは$2^j+1$以上の位置に格納されていることが分かり、$j \leftarrow j + 1$として同様に探索を続けます。もし、$2^j$番目の値がkey以上であれば、keyは$2^j$以下に格納されてる事が分かります。またその前ステップで$2^{j-1}$番目の要素はkeyより小さいことが確定しているため、keyが格納されている範囲$[2^{j-1}+1 \ldots 2^j]$を第一フェーズの結果として返します。
このようにkeyが格納されている範囲を計算する際チェックする位置を指数的に大きくしていることから指数探索、exponential searchと呼ばれています。
第二フェーズ
第二フェーズでは、第一フェーズで確定した範囲を二分探索し、keyが格納された位置を返します。
計算量
第一フェーズのステップ数は$\lceil \log i \rceil$のため、第一フェーズは$O(\log i)$時間で動作します。
第二フェーズの探索範囲は$[2^{\lceil \log i \rceil-1}+1 \ldots 2^{\lceil \log i \rceil}]$となり、この範囲を二分探索するため、第二フェーズも$O(\log i)$時間となります。
以上から、指数探索のアルゴリズムは$O(\log i)$時間で動作します。
プログラム
C++で実装すると以下のようになります。
二分探索のlower_boundと同様のインターフェースで作りました。
template <class ForwardIterator, class T>
ForwardIterator esearch(ForwardIterator first, ForwardIterator last, const T& key) {
auto len = std::distance(first, last);
auto &prev = first;
auto cur = first + 1;
size_t dis = 1;
for (; dis < len && *cur < key; prev = cur, std::advance(cur, dis), dis *= 2);
return std::lower_bound(prev, dis < len ? cur : last, key);
};
速度比較
二分探索と指数探索の速度比較を行いました。
配列の長さが$n=2^{16}$で、keyが$[0, 2n-1]$（keys1）、keyが$[0, n-1]$（keys2）、keyが$[0, n/4-1]$（keys3）、keyが$[0, n/2^{14}-1]$（keys4）を指している場合の平均実行時間を計測しました1。
bsearchが二分探索、esearchが指数探索を意味してます。
#### range static (0, 65536)
average range is 65536.00
keys1
bsearch takes 112 msecs
esearch takes 129 msecs
499165/1000000 (0.50) hitted!
average index is 1.00
keys2
bsearch takes 165 msecs
esearch takes 192 msecs
999981/1000000 (1.00) hitted!
average index is 0.50
keys3
bsearch takes 137 msecs
esearch takes 152 msecs
1000000/1000000 (1.00) hitted!
average index is 0.13
keys4
bsearch takes 57 msecs
esearch takes 36 msecs
1000000/1000000 (1.00) hitted!
average index is 0.00
結果から見ると、keyが先頭に極端に片寄っているkeys4の場合は指数探索の方が高速で、それ以外は二分探索の方が高速な結果になりました。
-
追記：hitの過去形はhitです、hittedではありません。皆さん気をつけましょう。 ↩