CKTIS / C++
std::binary_search: Mitgliedschaft in einem geordneten Bereich prüfen
std::binary_search liefert, ob ein geordneter Bereich ein zum Schlüssel äquivalentes Element enthält.
Version: C++23
Syntax
template<class ForwardIt, class T>
constexpr bool binary_search(ForwardIt first, ForwardIt last, const T& value);
template<class ForwardIt, class T, class Compare>
constexpr bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp);std::binary_search aus <algorithm> untersucht [first, last) und liefert true, wenn nach dem Komparator ein Element zu value äquivalent ist. Position oder Anzahl von Duplikaten werden nicht geliefert; dafür dienen lower_bound oder equal_range.
Vorbedingung ist die Partitionierung für genau diesen Schlüssel in beiden Vergleichsrichtungen sowie Asymmetrie: Ist comp(e, value) wahr, muss comp(value, e) falsch sein. Vollständiges Sortieren mit derselben konsistenten Ordnung ist eine sichere hinreichende, aber für einen einzelnen Schlüssel nicht notwendige Bedingung. Erst eine Verletzung der Partitionierung oder Asymmetrie führt zu undefiniertem Verhalten. Ein leerer Bereich ergibt false.
Die Vergleichszahl ist logarithmisch. Bei Random-Access-Iteratoren gilt dies auch für Schritte, andere Iteratoren können linear viele Inkremente brauchen. Der Komparator muss eine konsistente Ordnung bilden und darf Elemente nicht verändern.
Beispiele
#include <algorithm>
#include <array>
#include <iostream>
int main() {
const std::array values{1, 3, 5, 7};
std::cout << std::binary_search(values.begin(), values.end(), 5) << '\n';
}
Ergebnis
1
std::binary_search → 1