名前空間
変種

    std::binary_search

    提供: cppreference.com
     
    C++
     
    アルゴリズムライブラリ
    制約付きアルゴリズムと範囲に対するアルゴリズム (C++20)
    コンセプトとユーティリティ: std::sortable, std::projected, ...
    制約付きアルゴリズム: std::ranges::copy, std::ranges::sort, ...
    実行ポリシー (C++17)
    非変更シーケンス操作
    (C++11)(C++11)(C++11)
    (C++17)
    変更シーケンス操作
    未初期化記憶域の操作
    分割操作
    ソート操作
    (C++11)
    (C++11)
    二分探索操作
    集合操作 (ソート済み範囲用)
    ヒープ操作
    (C++11)
    (C++11)
    最小/最大演算
    (C++11)
    (C++11)
    (C++17)

    順列
    数値演算
    C のライブラリ
     
    <tbody> </tbody> <tbody class="t-dcl-rev t-dcl-rev-num "> </tbody><tbody> </tbody> <tbody class="t-dcl-rev t-dcl-rev-num "> </tbody><tbody> </tbody>
    ヘッダ <algorithm> で定義
    (1)
    template< class ForwardIt, class T > bool binary_search( ForwardIt first, ForwardIt last, const T& value );
    		 (C++20未満)
    template< class ForwardIt, class T > constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value );
    		 (C++20以上)
    (2)
    template< class ForwardIt, class T, class Compare > bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );
    		 (C++20未満)
    template< class ForwardIt, class T, class Compare > constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );
    		 (C++20以上)
    See More

    value と等しい要素が範囲 [first, last) 内に現れるかどうか調べます。

    std::binary_search が成功するためには、範囲 [first, last) は少なくとも value に関して部分的に順序付けされていなければなりません。 つまり、以下の要件をすべて満たさなければなりません。

    • element < value または comp(element, value) について分割されている (つまり、その式が true となるすべての要素が、その式が false となるすべての要素よりも前にある)。
    • !(value < element) または !comp(value, element) について分割されている。
    • すべての要素について、 element < value または comp(element, value) が true であれば、 !(value < element) または !comp(value, element) も true である。

    完全にソートされた範囲はこれらの基準を満たします。

    1つめのバージョンは要素を比較するために operator< を使用し、2つめのバージョンは指定された比較関数 comp を使用します。

    引数

    first, last - 調べる要素の範囲
    value - 要素と比較する値
    comp - 第1引数が第2引数より小さい (つまり前に順序付けされる) 場合に ​true を返す二項述語。

    述語関数のシグネチャは以下と同等なものであるべきです。

    bool pred(const Type1 &a, const Type2 &b);

    シグネチャが const & を持つ必要はありませんが、関数は渡されたオブジェクトを変更してはなならず、値カテゴリに関わらず Type1 および Type2 型 (およびそれらの const 修飾された型) のすべての値を受理できなければなりません (そのため Type1 & は許されません。 また Type1 に対してムーブがコピーと同等でなければ Type1 も許されません (C++11以上))。
    型 Type1 および Type2 は、 T 型のオブジェクトが Type1 と Type2 の両方に暗黙に変換可能であり、 ForwardIt 型のオブジェクトの逆参照が Type1 と Type2 の両方に暗黙に変換可能なものでなければなりません。 ​

    型の要件
    -
    ForwardIt は LegacyForwardIterator の要件を満たさなければなりません。
    -
    Compare は BinaryPredicate の要件を満たさなければなりません。 Compare を満たす必要はありません。

    戻り値

    value と等しい要素が見つかれば true、そうでなければ false。

    計算量

    行われる比較の回数は first と last の距離の対数です (多くとも log
    2    (last - first) + O(1)     回の比較)。 しかし、 LegacyRandomAccessIterator でない場合、イテレータのインクリメント回数は線形になります。

    実装例

    1つめのバージョン 
    template<class ForwardIt, class T>
bool binary_search(ForwardIt first, ForwardIt last, const T& value)
{
    first = std::lower_bound(first, last, value);
    return (!(first == last) && !(value < *first));
}
    2つめのバージョン 
    template<class ForwardIt, class T, 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) && !(comp(value, *first)));
}

    例

    Run this code
    #include <iostream>
#include <algorithm>
#include <vector>

int main()
{
    std::vector<int> haystack {1, 3, 4, 5, 9};
    std::vector<int> needles {1, 2, 3};

    for (auto needle : needles) {
        std::cout << "Searching for " << needle << '\n';
        if (std::binary_search(haystack.begin(), haystack.end(), needle)) {
            std::cout << "Found " << needle << '\n';
        } else {
            std::cout << "no dice!\n";
        }
    }
}

    出力: 

    Searching for 1
Found 1
Searching for 2
no dice!
Searching for 3
Found 3

    欠陥報告

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

    DR 適用先 発行時の動作 正しい動作
    LWG 270 C++98 Compare was required to be a strict weak ordering only a partitioning is needed; heterogeneous comparisons permitted

    関連項目

    		 特定のキーに一致する要素の範囲を返します
    (関数テンプレート) [edit]