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 bereit, aber nur diesen gibt einen booleschen Wert zurück. 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:

template
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 
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.