Wie implementiert man einen binären Suchalgorithmus, der einen Iterator in C zurückgibt?

Binärer Suchalgorithmus, der einen Iterator in C zurückgibt

In C bietet der Algorithmus std::binary_search eine praktische Möglichkeit um eine binäre Suche für sortierte Container durchzuführen. Es wird jedoch nur ein boolescher Wert zurückgegeben, der angibt, ob das Element vorhanden ist, was für einige Anwendungen möglicherweise nicht ausreicht.

Anforderung für den Iterator-Returning-Algorithmus

Es besteht der Bedarf für ein binärer Suchalgorithmus, der einen Iterator zurückgibt, der auf das Ergebnis zeigt, und nicht einen booleschen Wert. Dadurch können Entwickler auf das tatsächlich gefundene Element zugreifen oder feststellen, ob es nicht im Container vorhanden ist.

Implementierung eines benutzerdefinierten binären Suchalgorithmus

Da es keine solche Funktion gibt In der Standardbibliothek verfügbar, kann eine benutzerdefinierte Implementierung mit anderen STL-Funktionen wie std::lower_bound, std::upper_bound oder std::equal_range erstellt werden .

Beispielimplementierung

Hier ist eine einfache Implementierung, die std::lower_bound:

<code class="cpp">template<class Iter, class T>
Iter binary_find(Iter begin, Iter end, T val)
{
    // Finds the lower bound in at most log(last - first) + 1 comparisons
    Iter i = std::lower_bound(begin, end, val);

    if (i != end &amp;&amp; !(val < *i))
        return i; // found
    else
        return end; // not found
}</code>

Alternativ: Verwenden eines std::set

Eine andere Option besteht darin, ein std::set zu verwenden, das sortierte Elemente verwaltet und eine Methode find(T key) bereitstellt, die einen Iterator für das angegebene Element zurückgibt . Dieser Ansatz ist jedoch möglicherweise nicht geeignet, wenn mehrere Instanzen desselben Elements im Container erforderlich sind.

Das obige ist der detaillierte Inhalt vonWie implementiert man einen binären Suchalgorithmus, der einen Iterator in C zurückgibt?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!