std::binary_search

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 を使用します。

[編集] 引数

[編集] 戻り値

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

[編集] 計算量

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

[編集] 実装例

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));
}

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)));
}

[編集] 例

#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++ 標準に遡って適用されました。

[編集] 関連項目