std::binary_search

Defined in header `<algorithm>`

template< class ForwardIt, class T > bool binary_search( ForwardIt first, ForwardIt last, const T& value );	(1)

template< class ForwardIt, class T, class Compare > bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );	(2)

ソート範囲[first, last)いるかどうかをチェックvalueに等しい要素が含まれています。最初のバージョンは、要素を比較するoperator<使用して、2番目のバージョンは、指定された比較関数compを使用しています.

first, last	-	検討する要素の範囲
value	-	に要素を比較する値
comp	-	比較関数. 最初の値が二つ目の値より小さい場合、 trueを返します. 比較関数のシグネチャは以下と同等でなければなりません. bool cmp(const Type1 &a, const Type2 &b); シグネチャは`const`を含まなくても構いませんが, 比較関数は渡されたオブジェクトを変更してはなりません. The type Type1 must be such that an object of type T can be implicitly converted to Type1. The type Type2 must be such that an object of type ForwardIt can be dereferenced and then implicitly converted to Type2.
型の要件
- `ForwardIt` は `ForwardIterator` の要求を満足しなければなりません。

[編集] 返り値

valueに等しい要素が見つかった場合はtrue。その他の場合はfalse。

[編集] 計算複雑性

firstlastとの間の距離の対数

[編集] 可能な実装

First version

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

Second version

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

[編集] 参考


equal_range	特定のキーと一致する要素の範囲を返します Original: returns range of elements matching a specific key The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. (関数テンプレート) [edit]

Jul	SEP	Jul
	14
2016	2017	2021

言語
コンセプト
ユーティリティライブラリ
ストリングスライブラリ
コンテナライブラリ
アルゴリズムライブラリ
イテレータライブラリ
ニューメリックスライブラリ
入力/出力ライブラリ
ローカライゼーションライブラリ
正規表現ライブラリ (C++11)
アトミック操作ライブラリ (C++11)
スレッドのサポートライブラリ (C++11)

cppreference.com

検索

名前空間

変種

表示

操作