C++ STL Binäre Suche

Verwenden Sie std::binary_search, wenn Sie wissen möchten, ob ein Wert in einem geordneten Bereich vorkommt. Die Funktion liefert als Ergebnis der Mitgliedschaftsprüfung einen booleschen Wert zurück; sie gibt weder den passenden Iterator noch die Anzahl passender Werte zurück. Sie eignet sich für einen Vektor, ein Array oder einen anderen Bereich mit geeigneten Iteratoren, sofern die Anforderungen an die Sortierung erfüllt sind.

Die Anforderungen von std::binary_search verstehen

Der durchsuchte Bereich muss entsprechend dem beim Suchen verwendeten Vergleich partitioniert sein. Im üblichen Fall bedeutet das, dass die Elemente aufsteigend und nach derselben Ordnung wie beim Standardvergleich sortiert sind. Ist der Bereich nicht entsprechend geordnet, ist das Ergebnis keine zuverlässige Aussage darüber, ob ein Wert enthalten ist. Auch wenn Sie den Bereich zunächst sortieren und anschließend Elemente ändern oder teilweise umordnen, kann die Voraussetzung verletzt sein.

Das Iteratorpaar beschreibt einen halboffenen Bereich, [first, last): first zeigt auf das erste berücksichtigte Element, während last auf die Position direkt hinter dem letzten Element zeigt und nicht zum Bereich gehört. Mit container.begin() und container.end() durchsuchen Sie den gesamten Container. Ein leerer Bereich ist zulässig und ergibt keinen Treffer. Bei einem Bereich mit einem Element gehört dieses zum Suchbereich, wenn first auf das Element zeigt und last direkt dahinter liegt.

Das Ergebnis ist true, wenn ein nach der verwendeten Ordnung gleichwertiges Element vorhanden ist, andernfalls false. Wenn Sie die Position benötigen, verwenden Sie eine Funktion wie std::lower_bound und prüfen Sie, ob der zurückgegebene Iterator ungleich last ist und der Wert als gleichwertig gilt. std::binary_search allein zeigt nicht an, welches von mehreren gleichen Elementen gefunden wurde.

std::binary_search mit einem sortierten Bereich verwenden

Binden Sie für die Funktion <algorithm>, für die Ausgabe <iostream> und für diesen Container <vector> ein. Das folgende vollständige Programm prüft einen vorhandenen und einen nicht vorhandenen Wert. Es verwendet das boolesche Ergebnis direkt, sodass beide Fälle ohne Iterator sichtbar werden. Die im unveränderten Beispiel angezeigten Bezeichnungen und Ausgaben bleiben englisch.

Führen Sie dieses Beispiel aus:

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    const std::vector<int> values{2, 4, 6, 8, 10};
    const bool has_six = std::binary_search(values.begin(), values.end(), 6);
    const bool has_seven = std::binary_search(values.begin(), values.end(), 7);

    std::cout << std::boolalpha
              << "6 found: " << has_six << '\n'
              << "7 found: " << has_seven << '\n';
}

6 found: true
7 found: false

Der Vektor ist bereits sortiert, und bei jedem Aufruf wird sein vollständiger Iteratorbereich übergeben. Ändern Sie eines der beiden Suchziele, um das Beispiel anzupassen. Achten Sie darauf, dass der Vektor weiterhin in der für die Suche erforderlichen Ordnung sortiert ist. Die Funktion sortiert den Bereich nicht selbst.

Mit einem benutzerdefinierten Vergleich suchen

Bei einem benutzerdefinierten Typ übergeben Sie einen Vergleich, der die Ordnung des Bereichs festlegt. Sortieren Sie den Bereich vor der Suche mit demselben Vergleich. In diesem Beispiel werden Datensätze nach dem Alter geordnet. Ein Datensatz gilt als vorhanden, wenn ein Datensatz mit demselben Alter vorkommt. Der Name ist kein Bestandteil der Gleichwertigkeitsregel dieses Vergleichs.

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

#include <algorithm>
#include <string>
#include <vector>

struct Person {
    std::string name;
    int age;
};

int main() {
    const auto by_age = [](const Person& left, const Person& right) {
        return left.age < right.age;
    };

    std::vector<Person> people{{"Alice", 30}, {"Bob", 25}, {"Charlie", 35}};
    std::sort(people.begin(), people.end(), by_age);

    const Person target{"", 25};
    const bool found = std::binary_search(
        people.begin(), people.end(), target, by_age);
    return found ? 0 : 1;
}

Der Vergleich vergleicht Werte, keine Iteratoren. Er muss die Ordnung festlegen, nach der der Bereich sortiert wird, und mit Vergleichen zwischen den Bereichselementen und dem Suchziel kompatibel sein. Hier gelten zwei Datensätze mit gleichem Alter bei dieser Suche als gleichwertig, auch wenn ihre Namen unterschiedlich sind. Muss die Anwendung diese Datensätze unterscheiden, nehmen Sie die unterscheidenden Felder in die Ordnung auf oder verwenden Sie eine andere Suchstrategie.

Häufige Fehler bei der binären Suche vermeiden

• Unsortierte Daten durchsuchen: Sortieren Sie den Bereich zuerst. Eine Sortierung nach einem Schlüssel und eine Suche mit einer anderen Ordnung erfüllen die Suchvoraussetzung nicht.
• last als Element behandeln: last ist ausgeschlossen. Verwenden Sie für eine Suche im gesamten Container container.end() und dereferenzieren Sie diesen Iterator nicht.
• Einen Iterator erwarten: Der Rückgabewert ist boolesch. Wenn Sie eine Position benötigen, verwenden Sie std::lower_bound und prüfen Sie dessen Ergebnis, bevor Sie es dereferenzieren.
• Einen unpassenden Vergleich verwenden: Sortierung und Suche müssen dieselbe Ordnung und Gleichwertigkeit zugrunde legen. Behandelt ein Vergleich zwei Datensätze als gleichwertig, prüft die Suche die Mitgliedschaft nach dieser Regel und nicht nach allen Feldern des Datensatzes.

Mit diesen Prüfungen lässt sich das Ergebnis sinnvoll interpretieren. Die Bibliothek führt die Suche aus, erkennt aber nicht, ob der Bereich nach einer anderen Ordnung vorbereitet wurde oder der Vergleich nicht zu den Daten passt.