namespace std {
template <class ForwardIterator, class T>
bool binary_search(ForwardIterator first,
ForwardIterator last,
const T& value); // (1) C++03
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++03
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
を返すものとして扱われる。
例
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
// binary_search で 4 を検索する場合、
// 4 より小さい物、4 と等しい物、4 より大きい物がその順に並んでいれば、
// 必ずしもソートされている必要はない。
std::vector<int> v = {3, 1, 4, 6, 5};
if (std::binary_search(v.begin(), v.end(), 4)) {
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));
}
参照
- LWG Issue 787. complexity of
binary_search
- C++03までの計算量が間違っていたので、C++11で修正。
- P0202R3 Add Constexpr Modifiers to Functions in
<algorithm>
and<utility>
Headers