HOWTO · C++
C++ STL Binäre Suche
Dieses Lernprogramm demonstriert die Verwendung des Binärsuchalgorithmus aus der C++ Standard Template Library.
Auf dieser Seite
C++ stellt uns eine fertige Funktion binary_search() zur Verfügung, so dass wir die Funktion nicht selbst implementieren müssen. Es ist eine sehr einfach zu verwendende und effizient implementierte Methode und nicht fehleranfällig.
C++ STL binary_search() Überblick
Syntax
DEFAULT
: template <class ForwardIterator, class T>
bool
binary_search(ForwardIterator first, ForwardIterator last, const T& val);
CUSTOM COMPARISON FUNCTION
: template <class ForwardIterator, class T, class Compare>
bool
binary_search(ForwardIterator first, ForwardIterator last, const T& val,
Compare comp);
Hier kann T einer der folgenden Werte sein: int, float, short, long, byte, char, double, und auch ein benutzerdefiniertes Object.
Es wird geprüft, ob ein Element innerhalb von [first, last) mit dem Zielelement X übereinstimmt, wobei der binäre Suchalgorithmus verwendet wird. Standardmäßig wird der less-than-Operator verwendet, um Elemente zu vergleichen, aber wir können auch unsere eigene benutzerdefinierte comp bereitstellen, wie in der zweiten Vorlage oben beschrieben.
Parameter
first |
Ein Vorwärts-Iterator, der auf das erste Element im angegebenen Array-Bereich zeigt. |
last |
Ein Vorwärts-Iterator, der auf das letzte Element im angegebenen Array-Bereich zeigt. |
comp |
Eine benutzerdefinierte binäre Prädikatsfunktion, die zwei Vorwärts-Iteratoren als Argumente akzeptiert und true zurückgibt, wenn die beiden Argumente in der richtigen Reihenfolge vorhanden sind. Sie verändert keine Argumente und folgt der strengen schwachen Reihenfolge, um die Elemente zu ordnen. |
val |
Das Zielelement, das wir innerhalb des angegebenen Array-Bereichs suchen. |
Zurück
Wenn das Zielelement gefunden wird, wird true zurückgegeben; andernfalls wird false zurückgegeben.
C++ Programm für binäre Suche
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v = {1, 2, 3, 4, 5, 6};
if (binary_search(v.begin(), v.end(), 5)) {
cout << "Element found" << endl;
} else {
cout << "Element not found" << endl;
}
return 0;
}
