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

はじめに：二分探索（バイナリサーチ）とは

二分探索（バイナリサーチ）は、配列の中央の値と目的の要素を比較し、その結果に応じて探索範囲を半分に絞り込んでいく検索アルゴリズムです。この処理を要素が見つかるまで繰り返すことで、高速な検索を実現します。

ただし、二分探索を適用するには配列がソート済みであることが前提条件となります。整列されていないデータに対しては使用できない点に注意しましょう。

二分探索の計算量は対数時間 O(log n) であり、非常に効率的です。そのため、プログラマーにとってはアルゴリズムを自前で実装するだけでなく、標準テンプレートライブラリ（STL）に用意された便利な関数を使いこなすことも重要です。本記事では、STLに含まれる二分探索関連の関数「lower_bound」「upper_bound」「binary_search」について、構文や具体例を交えて詳しく解説します。

lower_bound ― 指定要素以上の値が現れる最初の位置を取得

lower_bound は、指定した要素が見つかった位置（イテレータ）を返す関数です。正確には、「指定した値以上の要素が最初に現れる位置」を返します。

構文

lower_bound(start_pointer, end_pointer, element)

パラメータの説明：

• start_pointer：探索範囲の開始位置を示すイテレータ（ポインタ）
• end_pointer：探索範囲の終了位置を示すイテレータ（ポインタ）
• element：探索したい対象の要素

戻り値は、条件を満たす要素の位置を指すイテレータです。挙動は以下のように場合分けできます。

• 要素が配列内に1つだけ存在する場合：その要素の位置を返す
• 要素が複数存在する場合：最初の要素の位置を返す
• 要素が存在しない場合：その要素より大きい値の中で最小の要素の位置を返す

なお、インデックス（何番目か）を求めるには、返されたイテレータから配列の先頭位置（begin()）を減算します。

サンプルコード

#include<bits/stdc++.h>
using namespace std;
int main(){
    vector<int> sortedarray = {2 , 5, 7, 8 , 15, 20 };
    vector<int> sortedarray2 = {2, 3, 4, 6 , 9 , 23 };
    vector<int> sortedarray3 = {2 , 5, 7, 7 , 15, 20 };
    cout<<"The position of element 7 found using lower_bound function :";
    cout<<"\nCase 1 : When element is present in array but only once ";
    cout<<lower_bound(sortedarray.begin() , sortedarray.end(), 7) - sortedarray.begin();
    cout<<"\nCase 2 : When element is present more than one times in the array ";
    cout<<lower_bound(sortedarray3.begin() , sortedarray3.end(), 7) - sortedarray3.begin();
    cout<<"\nCase 3 : When element is not present in the array ";
    cout<<lower_bound(sortedarray2.begin() , sortedarray2.end(), 7) - sortedarray2.begin();
}

実行結果

The position of element 7 found using lower_bound function :
Case 1 : When element is present in array but only once 2
Case 2 : When element is present more than one times in the array 2
Case 3 : When element is not present in the array 4

結果の解説：

• Case 1：{2, 5, 7, 8, 15, 20} の場合、7はインデックス2に1つだけ存在するため「2」が返されます。
• Case 2：{2, 5, 7, 7, 15, 20} の場合、7が重複して存在しますが、最初の出現位置である「2」が返されます。
• Case 3：{2, 3, 4, 6, 9, 23} の場合、7は存在しませんが、7より大きい最小の値9の位置である「4」が返されます。

upper_bound ― 指定要素より大きい値が現れる最初の位置を取得

upper_bound は、渡した要素より大きい値が最初に現れる位置を返す関数です。lower_boundとの違いは「以上」か「より大きい」かという点です。

構文

upper_bound(start_pointer, end_pointer, element)

パラメータの説明：

• start_pointer：探索範囲の開始位置を示すイテレータ（ポインタ）
• end_pointer：探索範囲の終了位置を示すイテレータ（ポインタ）
• element：基準となる要素

戻り値は、指定した要素の値よりも大きい値を持つ最初の要素の位置を指すイテレータです。挙動は以下の通りです。

• 要素が配列内に1つだけ存在する場合：その次の（より大きい）要素の位置を返す
• 要素が複数存在する場合：最後の要素の次の位置を返す
• 要素が存在しない場合：その要素より大きい値の中で最小の要素の位置を返す

こちらも同様に、先頭位置（begin()）を減算することでインデックスを求められます。

サンプルコード

#include<bits/stdc++.h>
using namespace std;
int main(){
    vector<int> sortedarray = {2 , 5, 7, 8 , 15, 20 };
    vector<int> sortedarray2 = {2, 3, 4, 6 , 9 , 23 };
    vector<int> sortedarray3 = {2 , 5, 7, 7 , 15, 20 };
    cout<<"The position of element 7 found using upper_bound function :";
    cout<<"\nCase 1 : When element is present in array but only once ";
    cout<<upper_bound(sortedarray.begin() , sortedarray.end(), 7) - sortedarray.begin();
    cout<<"\nCase 2 : When element is present more than one times in the array ";
    cout<<upper_bound(sortedarray3.begin() , sortedarray3.end(), 7) - sortedarray3.begin();
    cout<<"\nCase 3 : When element is not present in the array ";
    cout<<upper_bound(sortedarray2.begin() , sortedarray2.end(), 7) - sortedarray2.begin();
}

実行結果

The position of element 7 found using upper_bound function :
Case 1 : When element is present in array but only once 3
Case 2 : When element is present more than one times in the array 4
Case 3 : When element is not present in the array 4

結果の解説：

• Case 1：{2, 5, 7, 8, 15, 20} の場合、7より大きい最初の値8の位置「3」が返されます。
• Case 2：{2, 5, 7, 7, 15, 20} の場合、重複する7の末尾の次、つまり15の位置「4」が返されます。
• Case 3：{2, 3, 4, 6, 9, 23} の場合、7より大きい最小の値9の位置「4」が返されます。

binary_search ― 要素の存在有無を判定

binary_search は、指定した要素がデータ構造内に存在するかどうかを判定する関数です。位置情報ではなく真偽値で結果を得たい場合に便利です。

構文

binary_search(start_pointer, end_pointer, element)

パラメータの説明：

• start_pointer：探索範囲の開始位置を示すイテレータ（ポインタ）
• end_pointer：探索範囲の終了位置を示すイテレータ（ポインタ）
• element：探索したい対象の要素

要素が構造内に存在すれば true を、存在しなければ false を返します。

サンプルコード

#include<bits/stdc++.h>
using namespace std;
int main(){
    vector<int> sortedarray = {6, 15, 21, 27, 39, 42};
    cout<<"The element to be found in the array is 21\n" ;
    if(binary_search(sortedarray.begin(), sortedarray.end(), 21))
        cout<<"The element is found";
    else
        cout<<"The element is not found";
        cout<<"\nThe element to be found in the array is 5\n" ;
    if(binary_search(sortedarray.begin(), sortedarray.end(), 5))
        cout<<"The element is found";
    else
        cout<<"The element is not found";
}

実行結果

The element to be found in the array is 21
The element is found
The element to be found in the array is 5
The element is not found

{6, 15, 21, 27, 39, 42} という配列では、21は存在するため true（found）、5は存在しないため false（not found）が返されています。

まとめ

C++のSTLが提供する二分探索関連の3つの関数を整理すると、以下のようになります。

これらの関数はすべて計算量 O(log n) で動作し、ソート済みコンテナ（vector、arrayなど）に対して利用できます。競技プログラミングや実務でのデータ処理において頻出のテクニックなので、ぜひ使いこなせるようにしておきましょう。