C++標準テンプレートライブラリ（STL）で使える二分探索の基本と使い方

二分探索（バイナリサーチ）は「対数探索」とも呼ばれる検索アルゴリズムで、ソート済みの配列から特定の要素を効率よく探し出す手法です。配列を再帰的に半分に分割しながら探索範囲を絞り込み、中央の位置に目的の要素が見つかればその位置を返し、見つからなければ分割と照合を繰り返します。探索のたびに候補が半分に減っていくため、計算量はO(log n)と非常に高速です。

二分探索の仕組み

このアルゴリズムは、ソート済み配列の中央の要素と、探したい要素を比較することで動作します。

探索対象の要素が中央の要素と等しい場合 → その要素のインデックス（位置）を返します。

探索対象の要素が中央の要素より大きい場合 → 配列の後半（中央の次の要素から末尾までの部分配列）を探索します。

探索対象の要素が中央の要素より小さい場合 → 配列の前半（先頭から中央の前の要素までの部分配列）を探索します。

この処理を、要素が見つかるか探索範囲がなくなるまで繰り返します。

構文

STLの標準的な二分探索を呼び出すには、次の構文を使用します。

binary_search(start_address, end_address, element)

パラメータ

start_address：配列の最初の要素のアドレス。

end_address：配列の最後の要素のアドレス。

element：配列内で見つけたい要素。

戻り値

binary_searchはブール値を返します。要素が配列内に見つかった場合はtrue（真）を、見つからなかった場合はfalse（偽）を返します。なお、見つかった要素のインデックス（位置）そのものを取得したい場合は、std::lower_boundやstd::upper_boundを組み合わせて使用します。

使用例

次のサンプルコードでは、配列をsortでソートした後、binary_searchで要素「4」を検索しています。

#include <algorithm>
#include <iostream>
using namespace std;
void printArray(int a[], int arraysize){
    for (int i = 0; i < arraysize; ++i)
        cout << a[i] << " ";
}
int main(){
    int arr[] = {1, 5, 9, 7, 3, 2, 0, 4};
    int sizeofarr = sizeof(arr)/sizeof(arr[0]);
    cout << "The Element of array are :\n";
    printArray(arr, sizeofarr);
    cout << "\nSorting Elements of array.";
    sort(arr, arr+sizeofarr);
    cout << "\nSorted array is : ";
    printArray(arr, sizeofarr);
    cout << "\nElement to be searched is 4";
    if(binary_search(arr, arr+sizeofarr, 4))
        cout << "\nElement found ";
    else
        cout << "\nElement not found";
}

実行結果

The Element of array are :
1 5 9 7 3 2 0 4
Sorting Elements of array.
Sorted array is : 0 1 2 3 4 5 7 9
Element to be searched is 4
Element found

このように、binary_searchを使えばソート済み配列に対する高速な要素検索を簡単に実装できます。二分探索を利用する際は、必ず配列が事前にソートされていることを確認してください。