Können Sie einen effizienten binären Suchalgorithmus in C implementieren, der einen Iterator zum Suchergebnis zurückgibt?

Suche nach einem effizienten binären Suchalgorithmus in C

Programmierer versuchen oft, effiziente binäre Suchalgorithmen zu implementieren, die die Vorteile der logarithmischen Zeitkomplexität bieten . Eine häufige Anforderung besteht darin, dass der Algorithmus einen Iterator zurückgibt, der auf das Suchergebnis zeigt, und nicht einen einfachen booleschen Wert, der dessen Existenz angibt.

Die C-Standardbibliothek stellt std::binary_search im Header, aber es wird nur ein boolescher Wert zurückgegeben. Wie der Fragesteller anmerkte, kann dies in Situationen frustrierend sein, in denen die Geschwindigkeit einer binären Suche gewünscht ist und die Daten bekanntermaßen sortiert sind.

Glücklicherweise gibt es alternative Implementierungen, die die gewünschte Funktionalität bieten. Eine beliebte Option ist die Verwendung eines benutzerdefinierten Algorithmus, der die Funktionen std::lower_bound, std::upper_bound oder std::equal_range nutzt. Hier ist eine vereinfachte Version einer solchen Implementierung:

<code class="cpp">template<class Iter, class T>
Iter binary_find(Iter begin, Iter end, T val) {
    // Determine the lower bound using binary search
    Iter i = std::lower_bound(begin, end, val);

    // If the element is found, return the iterator to it
    if (i != end && !(val < *i)) {
        return i;
    }

    // Otherwise, return the end iterator
    else {
        return end;
    }
}</code>

Alternativ kann ein std::set verwendet werden, das die Reihenfolge der Elemente garantiert und die Find-Methode bereitstellt, die einen Iterator zum gewünschten Element zurückgibt. Es ist jedoch wichtig zu prüfen, ob die Anforderungen mit der Verwendung eines Satzes kompatibel sind, insbesondere in Fällen, in denen mehrere Instanzen desselben Elements gespeichert werden müssen.

Das obige ist der detaillierte Inhalt vonKönnen Sie einen effizienten binären Suchalgorithmus in C implementieren, der einen Iterator zum Suchergebnis zurückgibt?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!