C++ STLの二分探索関数の使い方｜binary_search・lower_bound・upper_bound徹底解説

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

二分探索（バイナリサーチ）は、ソート済みの配列から特定の値が存在する位置を効率的に見つけ出す検索アルゴリズムです。探索範囲の中央にある要素と目的の値を比較し、大小関係に応じて探索範囲を半分ずつ絞り込んでいくことで高速な検索を実現します。

先頭から順に調べる線形探索の計算量が O(n) であるのに対し、二分探索の計算量は O(log n) と非常に効率的です。データ件数が100万件あっても、比較回数はわずか20回程度で済みます。

C++のSTL（標準テンプレートライブラリ）には、この二分探索を簡単に利用できる関数が複数用意されています。本記事では、それぞれの使い方をサンプルコードとともに解説します。

C++ STLで使える二分探索系の関数

C++ STLで利用できる主な二分探索関連の関数は以下の3つです。いずれもコンテナが昇順にソートされていることが前提となる点に注意してください。

各関数の詳細な挙動

• binary_search(start, end, value)
  値が配列内に存在すれば true を、存在しなければ false を返します。
• lower_bound(start, end, value)
  値が1つだけ含まれる場合は「その値の位置」、複数含まれる場合は「最初に出現する位置」、値が存在しない場合は「その値より大きい最初の要素の位置（＝挿入すべき位置）」を指すポインタ（イテレータ）を返します。
• upper_bound(start, end, value)
  値が1つだけ含まれる場合は「その値より大きい次の要素の位置」、複数含まれる場合は「最後の出現位置の直後」、値が存在しない場合は「その値より大きい最初の要素の位置」を指すポインタ（イテレータ）を返します。

アルゴリズムの手順

Begin
　　整数型のvectorを初期化する
　　使用する関数：
　　binary_search(start_pointer, end_pointer, value)
　　　　→ 値が配列内に存在すれば true、なければ false を返す

　　lower_bound(start_pointer, end_pointer, value)
　　　　→ 値が1つだけある場合：「その値の位置」を返す
　　　　→ 値が複数ある場合：「最初の出現位置」を返す
　　　　→ 値がない場合：「その値より大きい次の数の位置」を返す

　　upper_bound(start_pointer, end_pointer, value)
　　　　→ 値が1つだけある場合：「その値より大きい次の数の位置」を返す
　　　　→ 値が複数ある場合：「最後の出現位置の直後」を返す
　　　　→ 値がない場合：「その値より大きい次の数の位置」を返す
　　結果を出力する
End

サンプルコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a = {6, 7, 10, 14, 16, 20};

    if (binary_search(a.begin(), a.end(), 50))
        cout << "50はvector内に存在します";
    else
        cout << "50は存在しません";
    cout << endl;

    if (binary_search(a.begin(), a.end(), 7))
        cout << "7はvector内に存在します";
    else
        cout << "7は存在しません";
    cout << endl;

    cout << "lower_boundによる7の位置: ";
    cout << lower_bound(a.begin(), a.end(), 7) - a.begin();
    cout << endl;

    cout << "upper_boundによる7の位置: ";
    cout << upper_bound(a.begin(), a.end(), 7) - a.begin();
    cout << endl;
}

実行結果

50は存在しません
7はvector内に存在します
lower_boundによる7の位置: 1
upper_boundによる7の位置: 2

実行結果の解説

このプログラムでは、ソート済みのvector a = {6, 7, 10, 14, 16, 20} に対して操作を行っています。

• binary_search に 50 を渡した場合、vector内に存在しないため else 側の処理が実行され、「50は存在しません」と表示されます。
• 7 はインデックス1に存在するため、「7はvector内に存在します」と表示されます。
• lower_bound は 7以上の最初の要素（＝7自身）の位置を返すため、インデックス 1 が出力されます。
• upper_bound は 7より大きい最初の要素（＝10）の位置を返すため、インデックス 2 が出力されます。

戻り値はイテレータであるため、- a.begin() を行うことでインデックス（何番目の要素か）に変換して表示しています。

注意点

• これらの関数を使用する前に、対象のコンテナは必ず昇順にソートしておきましょう。未ソートのまま使うと誤った結果になります。
• lower_bound / upper_bound の戻り値はイテレータなので、位置（インデックス）が必要な場合は begin() との差分を取ります。
• 値が見つからない場合でもエラーにはならず、挿入すべき適切な位置のイテレータが返されるため、ソート状態を保ちながら要素を挿入する用途にも活用できます。