std:: binary_search

From cppreference.net

Definiert in Header `<algorithm>`
	(1)
template < class ForwardIt, class T > bool binary_search ( ForwardIt first, ForwardIt last, const T & value ) ;			(constexpr seit C++20) (bis 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 ) ;			(seit C++26)
		(2)
template < class ForwardIt, class T, class Compare > bool binary_search ( ForwardIt first, ForwardIt last, const T & value, Compare comp ) ;				(constexpr seit C++20) (bis 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 ) ;				(seit C++26)

Überprüft, ob ein Element, das äquivalent zu value ist, innerhalb des partitionierten Bereichs [ first , last ) erscheint.

1) Die Äquivalenz wird mittels operator < geprüft:

Falls ! bool ( * iter < value ) && ! bool ( value < * iter ) für einen Iterator iter in [ first , last ) true ist, wird true zurückgegeben. Andernfalls wird false zurückgegeben.

Wenn eine der folgenden Bedingungen erfüllt ist, ist das Verhalten undefiniert:

Für irgendein Element elem in [ first , last ) impliziert bool ( elem < value ) nicht ! bool ( value < elem ) .
Die Elemente elem in [ first , last ) sind nicht bezüglich der Ausdrücke bool ( elem < value ) und ! bool ( value < elem ) partitioniert .

(bis C++20)

Entspricht std :: binary_search ( first, last, value, std:: less { } ) .

(seit C++20)

2) Die Äquivalenz wird unter Verwendung von comp überprüft:

Wenn ! bool ( comp ( * iter, value ) ) && ! bool ( comp ( value, * iter ) ) für einen Iterator iter in

first

last

true ist, gibt true zurück. Andernfalls gibt false zurück.

Wenn eine der folgenden Bedingungen erfüllt ist, ist das Verhalten undefiniert:

Für irgendein Element elem von [ first , last ) , bool ( comp ( elem, value ) ) impliziert nicht ! bool ( comp ( value, elem ) ) .
Die Elemente elem von [ first , last ) sind nicht partitioniert bezüglich der Ausdrücke bool ( comp ( elem, value ) ) und ! bool ( comp ( value, elem ) ) .

Inhaltsverzeichnis

Parameter

first, last	-	das Paar von Iteratoren, das den partitionierten Bereich der zu untersuchenden Elemente definiert
value	-	Wert, mit dem die Elemente verglichen werden
comp	-	binäres Prädikat, das true zurückgibt, wenn das erste Argument vor dem zweiten geordnet ist. Die Signatur der Prädikatfunktion sollte äquivalent zu Folgendem sein: bool pred ( const Type1 & a, const Type2 & b ) ; Obwohl die Signatur nicht const & benötigt, darf die Funktion die übergebenen Objekte nicht modifizieren und muss alle Werte des Typs (möglicherweise const) `Type1` und `Type2` unabhängig von der Wertkategorie akzeptieren können (daher ist Type1 & nicht erlaubt , ebenso wenig wie Type1 , es sei denn, für `Type1` ist eine Verschiebung äquivalent zu einer Kopie (seit C++11) ). Die Typen Type1 und Type2 müssen so beschaffen sein, dass ein Objekt vom Typ T implizit sowohl in Type1 als auch in Type2 konvertiert werden kann, und ein Objekt vom Typ ForwardIt dereferenziert und dann implizit sowohl in Type1 als auch in Type2 konvertiert werden kann.
Typanforderungen
- `ForwardIt` muss die Anforderungen von LegacyForwardIterator erfüllen.
- `Compare` muss die Anforderungen von BinaryPredicate erfüllen. Es muss nicht Compare erfüllen.

Rückgabewert

true wenn ein Element äquivalent zu value gefunden wurde, false andernfalls.

Komplexität

Gegeben $\scriptsize N$ $N$ als std:: distance ( first, last ) :

1) Höchstens

log 2 (N)+O(1)

Vergleiche mit value unter Verwendung von operator < (bis C++20) std:: less { } (seit C++20) .

2) Höchstens

log 2 (N)+O(1)

Anwendungen des Vergleichsoperators comp .

Wenn jedoch ForwardIt kein LegacyRandomAccessIterator ist, ist die Anzahl der Iterator-Inkremente linear in $\scriptsize N$ $N$ .

Hinweise

Obwohl std::binary_search lediglich erfordert, dass [ first , last ) partitioniert ist, wird dieser Algorithmus üblicherweise in Fällen verwendet, in denen [ first , last ) sortiert ist, sodass die binäre Suche für jeden value gültig ist.

std::binary_search prüft nur, ob ein äquivalentes Element existiert. Um einen Iterator auf dieses Element zu erhalten (falls vorhanden), std::lower_bound sollte stattdessen verwendet werden.

Feature-Test Makro	Wert	Std	Feature
`__cpp_lib_algorithm_default_value_type`	`202403`	(C++26)	Listeninitialisierung für Algorithmen ( 1,2 )

Mögliche Implementierung

Siehe auch die Implementierungen in libstdc++ und 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)));
}

**Anmerkung:** Der C++-Code in den `

`-Tags wurde gemäß den Anweisungen nicht übersetzt. Die Übersetzung betrifft nur die beschreibenden Textelemente, die in diesem Fall jedoch ausschließlich aus Links und C++-Code bestehen.

Beispiel

Diesen Code ausführen

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

Ausgabe:

Searching for 1
Found 1
Searching for 2
Not found!
Searching for 3
Found 3

Fehlerberichte

Die folgenden verhaltensändernden Fehlerberichte wurden rückwirkend auf zuvor veröffentlichte C++-Standards angewendet.

DR	Angewendet auf	Verhalten wie veröffentlicht	Korrigiertes Verhalten
LWG 270	C++98	`Compare` musste Compare erfüllen und `T` musste LessThanComparable sein (strikte schwache Ordnung erforderlich)	nur Partitionierung erforderlich; heterogene Vergleiche erlaubt
LWG 787	C++98	höchstens $log 2 (N)+2$ Vergleiche waren erlaubt	korrigiert zu $log 2 (N)+O(1)$

Siehe auch

equal_range	gibt den Bereich der Elemente zurück, die einem bestimmten Schlüssel entsprechen (Funktions-Template)
lower_bound	gibt einen Iterator zum ersten Element zurück, das nicht kleiner als der gegebene Wert ist (Funktions-Template)
upper_bound	gibt einen Iterator zum ersten Element zurück, das größer als ein bestimmter Wert ist (Funktions-Template)
ranges::binary_search (C++20)	bestimmt, ob ein Element in einem teilweise geordneten Bereich existiert (Algorithmus-Funktionsobjekt)

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

cppreference.net

Namespaces

Variants