Wie implementiert man einen binären Suchalgorithmus in C, der die Position des Elements zurückgibt?

Erhalten eines „nützlichen“ C-Binärsuchalgorithmus

Die C-STL stellt einen Binärsuchalgorithmus bereit, gibt aber nur einen booleschen Wert zurück, der angibt, ob der Element existiert. Für Fälle, in denen die genaue Position des Elements erforderlich ist, besteht Bedarf an einem umfassenderen Algorithmus.

Eine Möglichkeit besteht darin, eine benutzerdefinierte binäre Suchfunktion zu erstellen. Hier ist eine einfache Implementierung:

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

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

Ein anderer Ansatz ist die Verwendung eines std::set, das Elemente automatisch ordnet und eine find(T-Taste)-Methode bereitstellt, die einen Iterator für das Element zurückgibt. Dies ist jedoch möglicherweise nicht geeignet, wenn die Daten doppelte Werte enthalten können.

In Situationen, in denen es auf Geschwindigkeit ankommt, ist es wichtig, die Vorteile einer binären Suche zu nutzen. Die Algorithmen „Lower_bound“ und „upper_bound“ können unzureichend sein, wenn das Element nicht vorhanden ist, da sie möglicherweise nicht den Enditerator zurückgeben. Die oben bereitgestellte Funktion „binary_find“ behebt dieses Problem und stellt das korrekte Verhalten sicher.

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