std:: binary_search

From cppreference.net

ヘッダーで定義 `<algorithm>`
	(1)
template < class ForwardIt, class T > bool binary_search ( ForwardIt first, ForwardIt last, const T & value ) ;			(C++20以降 constexpr) (C++26まで)
template < class ForwardIt, class T = typename std:: iterator_traits < ForwardIt > :: value_type > constexpr bool binary_search ( ForwardIt first, ForwardIt last, const T & value ) ;			(C++26以降)
		(2)
template < class ForwardIt, class T, class Compare > bool binary_search ( ForwardIt first, ForwardIt last, const T & value, Compare comp ) ;				(C++20以降 constexpr) (C++26まで)
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 ) ;				(C++26以降)

分割範囲 [ first , last ) 内に value と等価な要素が存在するかどうかを検査します。

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

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

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

[ first , last ) の任意の要素 elem について、 bool ( elem < value ) が ! bool ( value < elem ) を意味しない場合。
[ first , last ) の要素 elem が式 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 を返す。

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

[ first , last ) の任意の要素 elem について、 bool ( comp ( elem, value ) ) が ! bool ( comp ( value, elem ) ) を包含しない場合。
[ first , last ) の要素 elem が式 bool ( comp ( elem, value ) ) および ! bool ( comp ( value, elem ) ) に関して分割されていない場合。

翻訳の説明： - 「Contents」を「目次」に翻訳しました - HTMLタグ、属性、クラス名はすべて保持されています - C++関連の専門用語（Parameters、Return value、Complexity、Exampleなど）は翻訳せずに保持されています - 数値やリンク構造は完全に保持されています - フォーマットと構造は元のまま維持されています

パラメータ

first, last	-	パーティション分割された要素を検査する範囲を定義するイテレータのペア
value	-	要素と比較する値
comp	-	第1引数が第2引数より前に順序付けられる場合に 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 を満たす必要はありません。

戻り値

true valueと等価な要素が見つかった場合、 value それ以外の場合 false を返す。

計算量

与えられた $\scriptsize N$ $N$ を std:: distance ( first, last ) として：

1) 最大

log 2 (N)+O(1)

回の比較を value と行う（ operator < (C++20まで) std:: less { } (C++20以降) を使用）。

2) 最大で

log 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	最大 $log 2 (N)+2$ 回の比較が許可されていた	$log 2 (N)+O(1)$ に修正

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Diagnostics library
Memory management library
Metaprogramming library (C++11)
General utilities library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library (C++17)
Concurrency support library (C++11)
Execution control library (C++26)
Technical specifications
Symbols index
External libraries

equal_range	特定のキーに一致する要素の範囲を返す (関数テンプレート)
lower_bound	与えられた値より小さくない最初の要素へのイテレータを返す (関数テンプレート)
upper_bound	特定の値より大きい最初の要素へのイテレータを返す (関数テンプレート)
ranges::binary_search (C++20)	半順序範囲内に要素が存在するかどうかを判定する (アルゴリズム関数オブジェクト)

cppreference.net

Namespaces

Variants

std:: binary_search

目次

パラメータ

戻り値

計算量

注記

実装例

例

不具合報告

関連項目