std::binary_search

ヘッダ `<algorithm>`
template< class ForwardIt, class T > bool binary_search( ForwardIt first, ForwardIt last, const T& value );	で定義 (1)	(C++26 まで) (C++20 から constexpr)
template< class ForwardIt, class T = typename std::iterator_traits <ForwardIt>::value_type > constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value );	で定義 (1)		(C++26 から)
template< class ForwardIt, class T, class Compare > bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );	(2)	(C++26 まで) (C++20 から constexpr)
template< class ForwardIt, class T = typename std::iterator_traits <ForwardIt>::value_type, class Compare > constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );	(2)		(C++26 から)

分割された範囲 value 内に [first, last) と同等の要素が存在するかチェックします。

1) 等価性は operator< を用いてチェックされます:

もし !bool(*iter < value) && !bool(value < *iter) が範囲 true 内のあるイテレータ iter に対して [first, last) である場合、true を返します。それ以外の場合は false を返します。

次の条件のいずれかが満たされる場合、動作は未定義です:

範囲 elem の任意の要素 [first, last) に対して、bool(elem < value) が !bool(value < elem) を意味しない。
範囲 elem の要素 [first, last) が、式およびに関してbool(elem < value)分割!bool(value < elem)されていない。

(C++20 まで)

std::binary_search(first, last, value, std::less{}) と同等です。

(C++20 から)

2) 等価性は comp を用いてチェックされます:

もし !bool(comp(*iter, value)) && !bool(comp(value, *iter)) が範囲 true 内のあるイテレータ iter に対して [first, last) である場合、true を返します。それ以外の場合は false を返します。

次の条件のいずれかが満たされる場合、動作は未定義です:

範囲 elem の任意の要素 [first, last) に対して、bool(comp(elem, value)) が !bool(comp(value, elem)) を意味しない。
範囲 elem の要素 [first, last) が、式およびに関してbool(comp(elem, value))分割!bool(comp(value, elem))されていない。

引数

first, last	-	調査する分割された範囲を定義するイテレータのペア
value	-	要素と比較する値
comp	-	1番目の引数が2番目の引数より前に順序付けされる場合に`true` true を返す二項述語。述語関数のシグネチャは以下と同等であるべきです: `bool pred(const Type1 &a, const Type2 &b);` シグネチャに `const &` を含む必要はありませんが、関数は渡されたオブジェクトを変更してはならず、型 (const の可能性がある) `Type1` および `Type2` のすべての値を値カテゴリにかかわらず受け入れられなければなりません (そのため、`Type1 &` は許可されません。また、`Type1` は `Type1` にムーブがコピーと同等である場合を除き許可されません(C++11 から))。型 `Type1` および `Type2` は、型 `T` のオブジェクトが `Type1` と `Type2` の両方に暗黙的に変換可能であり、型 `ForwardIt` のオブジェクトが逆参照されて `Type1` と `Type2` の両方に暗黙的に変換可能であるようにする必要があります。
型要件
- `ForwardIt` は LegacyForwardIterator の要件を満たす必要があります。
- `Compare` は BinaryPredicate の要件を満たす必要があります。Compare を満たす必要はありません。

戻り値

truevalue と同等の要素が見つかった場合は false true、それ以外の場合は false。

計算量

$\scriptsize N$ $N$ を std::distance(first, last) とすると:

1) 最大で

log 2 (N)+O(1)

回の value との比較 (C++20 までは)operator< (C++20 からは)std::less{}。2)

最大で $\scriptsize \log_{2}(N)+O(1)$

2 (N)+O(1) 回の比較器

の適用。comp

ただし、ForwardIt が LegacyRandomAccessIterator でない場合、イテレータのインクリメント回数は $\scriptsize N$ $N$ に比例します。

注記

std::binary_search は [first, last) が分割されていることのみを必要としますが、このアルゴリズムは通常、[first, last) がソートされている場合に使用され、任意の value に対して二分探索が有効になります。

std::binary_search は同等の要素が存在するかどうかのみをチェックします。その要素へのイテレータを取得するには (存在する場合)、代わりに std::lower_bound を使用すべきです。

機能テストマクロ	値	規格	機能
`__cpp_lib_algorithm_default_value_type`	`202403`	(C++26)	アルゴリズムのためのリスト初期化 (1,2)

実装例

実装は libstdc++ および libc++ も参照してください。

binary_search (1)

template<class ForwardIt, class T = typename std::iterator_traits<ForwardIt>::value_type>
bool binary_search(ForwardIt first, ForwardIt last, const T& value)
{
    return std::binary_search(first, last, value, std::less{});
}

binary_search (2)

template<class ForwardIt, class T = typename std::iterator_traits<ForwardIt>::value_type,
         class Compare>
bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    first = std::lower_bound(first, last, value, comp);
    return (!(first == last) and !(comp(value, *first)));
}

例

このコードを実行する

#include <algorithm>
#include <cassert>
#include <complex>
#include <iostream>
#include <vector>

int main()
{
    const auto haystack = {1, 3, 4, 5, 9};
    
    for (const auto needle : {1, 2, 3})
    {
        std::cout << "Searching for " << needle << '\n';
        if (std::binary_search(haystack.begin(), haystack.end(), needle))
            std::cout << "Found " << needle << '\n';
        else
            std::cout << "Not found!\n";
    }

    using CD = std::complex<double>;
    std::vector<CD> nums{{1, 1}, {2, 3}, {4, 2}, {4, 3}};
    auto cmpz = [](CD x, CD y){ return abs(x) < abs(y); };
    #ifdef __cpp_lib_algorithm_default_value_type
        assert(std::binary_search(nums.cbegin(), nums.cend(), {4, 2}, cmpz));
    #else
        assert(std::binary_search(nums.cbegin(), nums.cend(), CD{4, 2}, cmpz));
    #endif
}

出力:

Searching for 1
Found 1
Searching for 2
Not found!
Searching for 3
Found 3

欠陥報告

以下の動作変更欠陥報告は、以前に公開された C++ 標準に遡って適用されました。

DR	適用先	公開された動作	正しい動作
LWG 270	C++98	`Compare` は Compare を満たす必要があり、`T` は LessThanComparable (狭義弱順序が必要) である必要がありました	分割のみが必要; 異種比較が許可される
LWG 787	C++98	最大で $\scriptsize \log_{2}(N)+2$ $log 2 (N)+2$ の比較が許可されていました	$\scriptsize \log_{2}(N)+O(1)$ $log 2 (N)+O(1)$

に修正されました関連項目

equal_range	二分探索を使用して指定された値に一致する要素の範囲を検索します (関数テンプレート & アルゴリズム関数オブジェクト)
ranges::equal_range (C++20)	二分探索を使用して指定された値に一致する要素の範囲を検索します (関数テンプレート & アルゴリズム関数オブジェクト)
lower_bound	二分探索を使用して指定された値より小さくない最初の要素を検索します (関数テンプレート & アルゴリズム関数オブジェクト)
ranges::lower_bound (C++20)
upper_bound	二分探索を使用して指定された値より大きい最初の要素を検索します (関数テンプレート & アルゴリズム関数オブジェクト)
ranges::upper_bound (C++20)	二分探索を使用して指定された値より大きい最初の要素を検索します (関数テンプレート & アルゴリズム関数オブジェクト)
ranges::binary_search (C++20)	二分探索を使用して範囲内に要素が存在するかどうかを判定します (アルゴリズム関数オブジェクト)

コンパイラサポート
フリースタンディングとホスト環境
言語
標準ライブラリ
標準ライブラリヘッダ
名前付き要件
機能テストマクロ (C++20)
言語サポートライブラリ
コンセプトライブラリ (C++20)
診断ライブラリ
メモリ管理ライブラリ
メタプログラミングライブラリ (C++11)
汎用ユーティリティライブラリ
コンテナライブラリ
イテレータライブラリ
レンジライブラリ (C++20)
アルゴリズムライブラリ
文字列ライブラリ
テキスト処理ライブラリ
数値ライブラリ
日付と時刻ライブラリ
入出力ライブラリ
ファイルシステムライブラリ (C++17)
並行性サポートライブラリ (C++11)
実行制御ライブラリ (C++26)
技術仕様
シンボルインデックス
外部ライブラリ

ja.cppreference.net

Namespaces

Variants

std::binary_search

目次

引数

戻り値

計算量

注記

実装例

例

欠陥報告

に修正されました関連項目