名前空間
変種
操作

std::binary_search

提供: cppreference.com
< cpp‎ | algorithm
 
 
アルゴリズムライブラリ
実行ポリシー (C++17)
非変更シーケンス操作
(C++11)(C++11)(C++11)
(C++17)
変更シーケンス操作
未初期化記憶域の操作
分割操作
ソート操作
(C++11)
二分探索操作
binary_search
集合操作 (ソート済み範囲用)
ヒープ操作
(C++11)
最小/最大演算
(C++11)
(C++17)
順列
数値演算
C のライブラリ
 
ヘッダ <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およびそれ以降)

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

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

  • element < value または comp(element, value) について分割されている。
  • !(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 は、 T 型のオブジェクトが Type1Type2 の両方に暗黙に変換可能であり、 ForwardIt 型のオブジェクトの逆参照が Type1Type2 の両方に暗黙に変換可能なものでなければなりません。 ​

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

[編集] 戻り値

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

[編集] 計算量

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

[編集] 実装例

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

[編集]

#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]