二分探索（バイナリサーチ）のアルゴリズムとC++実装をわかりやすく解説

リストがソート（整列）されている場合、二分探索（バイナリサーチ）という手法を使うことで、目的の要素を高速に見つけることができます。この手法では、まずリスト全体を中央の要素を境に左右の部分リストに分割します。中央の要素が探索キーと一致すればその位置を返し、一致しない場合はキーの大小に応じて左側または右側の部分リストへと探索範囲を絞り込みます。この処理を、要素が見つかるか探索範囲がなくなるまで繰り返すのが二分探索の基本的な流れです。

二分探索の計算量

• 時間計算量： 最良ケースは O(1)、平均ケース・最悪ケースは O(log₂ n)
• 空間計算量： O(1)

二分探索では探索のたびに候補範囲が半分になるため、要素数が n 個のリストでも最大約 log₂ n 回の比較で目的の要素を見つけられます。例えば100万件のデータでも20回程度の比較で済むため、先頭から順に調べる線形探索（O(n)）と比べて非常に高速です。

入力と出力

入力：
ソート済みのデータリスト：12 25 48 52 67 79 88 93
探索キー：79
出力：
要素は位置 5 で見つかりました

アルゴリズム

binarySearch(array, start, end, key)

入力 − ソート済みの配列、探索範囲の開始位置と終了位置、探索キー

出力 − キーが見つかった場合はその位置、見つからない場合は無効な位置

Begin
    if start <= end then
        mid := start + (end - start) / 2
        if array[mid] = key then
            return mid location
        if array[mid] > key then
            call binarySearch(array, start, mid-1, key)
        else when array[mid] < key then
            call binarySearch(array, mid+1, end, key)
    else
        return invalid location
End

なお、中央位置の計算を mid = start + (end - start) / 2 としているのは、(start + end) / 2 と結果は同じでも、大きな値同士の加算によるオーバーフローを防ぐためです。大規模な配列を扱う実装ではこの書き方が推奨されます。

C++による実装例

#include<iostream>
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 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 = binarySearch(arr, 0, n, searchKey)) >= 0)
        cout << "Item found at location: " << loc << endl;
    else
        cout << "Item is not found in the list." << endl;
}

この実装では、再帰的に binarySearch 関数を呼び出すことで探索範囲を絞り込んでいます。キーが見つからなかった場合は -1 を返し、main 関数側で「見つからなかった」旨のメッセージを表示します。

実行結果

Enter number of items: 8
Enter items:
12 25 48 52 67 79 88 93
Enter search key to search in the list: 79
Item found at location: 5

まとめ

二分探索は、ソート済みのデータから目的の値を O(log n) の時間計算量で高速に検索できる強力なアルゴリズムです。データベースのインデックス検索や標準ライブラリの std::binary_search など、さまざまな場面で応用されています。ただし、事前にデータが整列されていることが前提となるため、ソートされていないデータに対しては事前にソート処理を行う必要がある点に注意しましょう。