指数探索（エクスポネンシャルサーチ）とは？仕組み・計算量・C++実装を徹底解説

指数探索（エクスポネンシャルサーチ）とは

指数探索（Exponential Search）は、「ダブリング探索」や「ギャロッピング探索」とも呼ばれる検索アルゴリズムです。まず、探索キーが存在する可能性のある範囲を大まかに絞り込み、その後、その狭い範囲に対して二分探索（バイナリサーチ）を適用してキーの正確な位置を特定します。

リストの下限を L、上限を U とすると、L と U はどちらも 2 のべき乗（1, 2, 4, 8, …）として増加していきます。最後の区間では、U がリストの末尾の位置になります。このように範囲を「2 のべき乗」で拡張していく動作から、「指数探索」という名前が付けられています。

動作の流れ

1. インデックス i を 1（2⁰）から始め、array[i] がキーより小さい間、i を 2 倍ずつ増やしていきます。
2. array[i] がキー以上になった時点で、キーは i/2 ～ i の間に存在する可能性が高いと判断できます。
3. その絞り込んだ範囲に対して二分探索を実行し、キーの正確な位置を求めます。

指数探索の計算量

• 時間計算量： 最良ケース O(1)。平均ケース・最悪ケースは O(log₂ i)（i は探索キーが存在する位置）。
• 空間計算量： O(1)

入出力例

入力：
ソート済みのデータ列：
10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995
探索キー：780

出力：
Item found at location: 16

アルゴリズム

binarySearch（二分探索）

入力： ソート済み配列、開始位置と終了位置、探索キー
出力： 見つかった場合はキーの位置、見つからない場合は不正な位置（-1）

Begin
    if start <= end then
        mid := start + (end - start) / 2
        if array[mid] = key then
            return mid（キーの位置）
        if array[mid] > key then
            call binarySearch(array, start, mid-1, key)   // 左半分を探索
        else if array[mid] < key then
            call binarySearch(array, mid+1, end, key)     // 右半分を探索
    else
        return invalid location（-1）
End

exponentialSearch（指数探索）

入力： ソート済み配列、開始位置と終了位置、探索キー
出力： 見つかった場合はキーの位置、見つからない場合は不正な位置（-1）

Begin
    if (end - start) <= 0 then
        return invalid location（-1）
    i := 1                              // 2^0 = 1 から開始
    while i < (end - start) do
        if array[i] < key then
            i := i * 2                  // i を 2 のべき乗として増加させる
        else
            terminate the loop          // array[i] がキー以上になったら終了
    done
    call binarySearch(array, i/2, min(i, end-1), key)   // 絞り込んだ範囲で二分探索
End

C++ による実装例

#include <iostream>
#include <algorithm>
using namespace std;

int binarySearch(int array[], int start, int end, int key) {
    if (start <= end) {
        int mid = start + (end - start) / 2; // リストの中央位置
        if (array[mid] == key)
            return mid;
        if (array[mid] > key)
            return binarySearch(array, start, mid - 1, key); // 左半分を探索
        return binarySearch(array, mid + 1, end, key);       // 右半分を探索
    }
    return -1;
}

int exponentialSearch(int array[], int start, int end, int key) {
    if ((end - start) <= 0)
        return -1;
    int i = 1;                        // 2^0 = 1 から開始
    while (i < (end - start) && array[i] < key)
        i *= 2;                       // i を 2 のべき乗として増加
    return binarySearch(array, i / 2, min(i, end - 1), key); // 範囲を絞って二分探索
}

int main() {
    int n, searchKey, loc;
    cout << "Enter number of items: ";
    cin >> n;
    int arr[n];                       // サイズ n の配列を作成
    cout << "Enter items: " << endl;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "Enter search key to search in the list: ";
    cin >> searchKey;
    if ((loc = exponentialSearch(arr, 0, n, searchKey)) >= 0)
        cout << "Item found at location: " << loc << endl;
    else
        cout << "Item is not found in the list." << endl;
}

実行結果

Enter number of items: 20
Enter items:
10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995
Enter search key to search in the list: 780
Item found at location: 16

まとめ

指数探索は、探索範囲を 2 のべき乗で倍々に拡大しながらおおよその位置を特定し、その後に二分探索で精密な位置を確定する効率的な探索手法です。要素数が事前にわからない無限リストやストリームの探索、あるいは目的の要素が配列の先頭付近にある場合には、通常の二分探索よりも少ない比較回数で高速に結果を得られるという大きな利点があります。