C++で二分探索（バイナリサーチ）を実装する方法を解説

二分探索（バイナリサーチ）とは

二分探索（Binary Search）は、ソート済みの配列から目的の要素を効率的に見つけ出すアルゴリズムです。探索範囲を繰り返し半分に絞り込んでいくことで、先頭から順に調べる線形探索よりもはるかに高速に検索できます。

具体的な手順は以下の通りです。

1. まず配列全体を探索対象とする
2. 配列の中央にある要素と目的の値を比較する
3. 目的の値が中央の要素より大きければ上半分を、小さければ下半分を次の探索範囲とする
4. 目的の値が見つかるか、探索範囲が空になるまで手順2〜3を繰り返す

この手法により計算量は O(log n) に抑えられ、大量のデータでも高速に探索できます。

C++による二分探索の実装例

以下は、C++で二分探索を実装したプログラムの例です。

#include <iostream>
using namespace std;

int binarySearch(int arr[], int p, int r, int num) {
    if (p <= r) {
        int mid = (p + r) / 2;
        if (arr[mid] == num)
            return mid;
        if (arr[mid] > num)
            return binarySearch(arr, p, mid - 1, num);
        if (arr[mid] < num)
            return binarySearch(arr, mid + 1, r, num);
    }
    return -1;
}

int main(void) {
    int arr[] = {1, 3, 7, 15, 18, 20, 25, 33, 36, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int num;
    cout << "Enter the number to search: \n";
    cin >> num;
    int index = binarySearch(arr, 0, n - 1, num);
    if (index == -1) {
        cout << num << " is not present in the array";
    } else {
        cout << num << " is present at index " << index << " in the array";
    }
    return 0;
}

実行結果

Enter the number to search:
20
20 is present at index 5 in the array

プログラムの解説

binarySearch() 関数の仕組み

binarySearch() は、二分探索によって配列内の目的の要素を見つけるための再帰関数です。引数として、配列・下限インデックス p・上限インデックス r・探したい値 num を受け取ります。

int binarySearch(int arr[], int p, int r, int num)

関数内では、まず配列の中央位置 mid を計算し、その要素と num を比較して処理を分岐させます。

• arr[mid] == num の場合： 目的の値が見つかったので、そのインデックス mid を返す
• arr[mid] > num の場合： 目的の値は左側にあるため、下限 p〜上限 mid-1 の範囲で自分自身を再帰的に呼び出す
• arr[mid] < num の場合： 目的の値は右側にあるため、下限 mid+1〜上限 r の範囲で自分自身を再帰的に呼び出す

int binarySearch(int arr[], int p, int r, int num) {
    if (p <= r) {
        int mid = (p + r) / 2;
        if (arr[mid] == num)
            return mid;
        if (arr[mid] > num)
            return binarySearch(arr, p, mid - 1, num);
        if (arr[mid] < num)
            return binarySearch(arr, mid + 1, r, num);
    }
    return -1;
}

p > r となって探索範囲が空になった場合は、値が配列内に存在しないことを示す -1 を返します。

main() 関数の処理

main() 関数では、ソート済みの配列 arr[] を定義し、sizeof を使って配列の要素数 n を求めます。その後、binarySearch() を呼び出して目的の値のインデックスを取得します。

• 戻り値が -1 の場合：値は配列内に存在しない
• 戻り値が -1 以外の場合：その値が目的の要素のインデックスである

int main(void) {
    int arr[] = {1, 3, 7, 15, 18, 20, 25, 33, 36, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int num = 33;
    int index = binarySearch(arr, 0, n - 1, num);
    if (index == -1)
        cout << num << " is not present in the array";
    else
        cout << num << " is present at index " << index << " in the array";
    return 0;
}

まとめ

二分探索は、ソート済みデータに対して O(log n) の計算量で高速に要素を検索できる強力なアルゴリズムです。C++では、このように再帰呼び出しを使うことで簡潔に実装できます。また、標準ライブラリの std::binary_search や std::lower_bound を利用すれば、自前で実装することなく二分探索の機能を活用することも可能です。