GeezerVison is showing cpprefjp.github.io — std::binary_search - cpprefjp C++日本語リファレンス
最終更新日時:
2026年09月11日 13時06分31秒 (JST)
Akira Takahashi
が更新
function template
<algorithm>
std:: binary_search
namespace std {
template < class ForwardIterator ,
class T >
bool
binary_search ( ForwardIterator first ,
ForwardIterator last ,
const T & value ); // (1) C++98
template < class ForwardIterator ,
class T >
constexpr bool
binary_search ( ForwardIterator first ,
ForwardIterator last ,
const T & value ); // (1) C++20
template < class ForwardIterator ,
class T ,
class Compare >
bool
binary_search ( ForwardIterator first ,
ForwardIterator last ,
const T & value ,
Compare comp ); // (2) C++98
template < class ForwardIterator ,
class T ,
class Compare >
constexpr bool
binary_search ( ForwardIterator first ,
ForwardIterator last ,
const T & value ,
Compare comp ); // (2) C++20
}
概要
イテレータ範囲[first, last)から、二分探索法によって条件一致する要素の検索を行う。
要件
[first,last) の要素 e は e < value および !(value < e)、または comp(e, value) および !comp(value, e) によって区分化 されていなければならない。
また、[first, last) の全ての要素 e は、e < value であれば !(value < e) である、または comp(e, value) であれば !comp(value, e) である必要がある。
戻り値
[first,last) 内のイテレータ i について、!(*i < value) && !(value < *i) または comp(*i, value) == false && comp(value, *i) == false であるようなイテレータが見つかった場合は true を返す。
計算量
最大で log2(last - first) + O(1) 回の比較を行う
備考
comp は 2 引数の関数オブジェクトで、1 番目の引数が 2 番目の引数「より小さい」場合に true を、そうでない場合に false を返すものとして扱われる。(1), (2) :
C++26 : 引数として波カッコ初期化{}を受け付ける
例
基本的な使い方
出力
found
波カッコ初期化を入力として使用する (C++26)
#include <algorithm>
#include <iostream>
#include <vector>
struct Point {
int x ;
int y ;
bool operator == ( const Point & other ) const = default ;
auto operator <=> ( const Point & other ) const = default ;
};
int main () {
std::vector < Point > v = {
{ 1 , 2 },
{ 3 , 4 },
{ 5 , 6 },
};
// 値{3, 4}を二分検索
bool found = std::binary_search ( v.begin() , v.end() , { 3 , 4 });
if ( found ) {
std::cout << "found" << std::endl ;
}
else {
std::cout << "not found" << std::endl ;
}
}
出力
found
実装例
template < class ForwardIterator , class T >
bool binary_search ( ForwardIterator first , ForwardIterator last ,
const T & value )
{
first = std::lower_bound ( first , last , value );
return first != last && ! bool ( value < * first );
}
template < class ForwardIterator , class T , class Compare >
bool binary_search ( ForwardIterator first , ForwardIterator last ,
const T & value , Compare comp )
{
first = std::lower_bound ( first , last , value , comp );
return first != last && ! bool ( comp ( value , * first ));
}
バージョン
言語
処理系
関連項目
参照