標準 C++ ライブラリには、さまざまな 2 等分探索アルゴリズムが用意されています。これらのアルゴリズムはすべて、近似 log n 比較だけを実行します。この n は、引数によって記述される範囲内の要素数です。これらのアルゴリズムは、vector や deque から生成されるような、ランダムアクセス反復子に適用されるときが最も効率的で、この場合も総じて近似 log n 演算を実行します。ただし、list により生成されるような非ランダムアクセス反復子にも適用され、この場合は一次数のステップを実行します。2 等分探索を set または multiset データ構造に適用することは、正当ではあっても必要というわけではありません。これは、これらのコンテナクラスには独自の検索方法があり、そのほうが効率的だからです。
汎用アルゴリズム binary_search() は、シーケンスに引数と等価の値が含まれる場合は true を返します。等価であるとは、Compare(value, arg) と Compare(arg, value) がいずれも false であることです。このアルゴリズムは次のように宣言されます。
bool binary_search (ForwardIterator first, ForwardIterator last,
const T & value [, Compare ] );
また、一致する値の位置を知ることが重要な場合もあります。この情報は、次のように定義されるアルゴリズムのコレクションによって返されます。
ForwardIterator last, const T& value [ , Compare ] );
ForwardIterator upper_bound (ForwardIterator first,
ForwardIterator last, const T& value [, Compare ] );
pair<ForwardIterator, ForwardIterator> equal_range
(ForwardIterator first, ForwardIterator last,
const T& value [, Compare ] );
アルゴリズム lower_bound() は、反復子として、順序を変えずに引数を挿入できる最初の位置を返しますが、アルゴリズム upper_bound() は、最後の位置を検出します。これらが一致するのは、要素が現在シーケンス内にない場合に限られます。これらのアルゴリズムは、反復子の対を返すアルゴリズム equal_range() で共に実行することができます。
プログラム例では、これらの関数は乱数 vector に使用されています。
void binary_search_example ()
// 2 等分探索アルゴリズムの使用方法を説明する
// 完全ソースコードについては alg7.cpp を参照
{
// 15 の乱数を含む順序ベクトルを作成する
vector<int> aVec(15);
generate (aVec.begin(), aVec.end(), randomValue);
sort (aVec.begin(), aVec.end());
// 11 が含まれているかどうかを調べる
if (binary_search (aVec.begin(), aVec.end(), 11))
cout << "contains an 11" << endl;
else
cout << "does not contain an 11" << endl;
// 11 と 14 を挿入する
vector<int>::iterator where;
where = lower_bound (aVec.begin(), aVec.end(), 11);
aVec.insert (where, 11);
where = upper_bound (aVec.begin(), aVec.end(), 14);
aVec.insert (where, 14);
}