Wie finde ich einen Elementindex mit der binären Suche in C?

Effiziente binäre Suchimplementierung in C

Das Finden des Index oder Iterators eines Elements in einem sortierten Container ist eine grundlegende Operation in C. Der std::binary_search-Algorithmus der Standardbibliothek gibt jedoch nur einen booleschen Wert zurück, der die Existenz des Elements angibt, nicht seine Position.

Betrachten Sie den Fall, in dem der Container sortiert ist, und aus Effizienzgründen ist ein binärer Suchalgorithmus vorzuziehen . Es ist eine Implementierung erforderlich, die diesen Bedarf berücksichtigt.

Benutzerdefinierte iterative binäre Suche

Ein Ansatz besteht darin, einen benutzerdefinierten iterativen binären Suchalgorithmus zu implementieren. Hier ist eine Beispielimplementierung:

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

Dieser Algorithmus verwendet std::lower_bound, um effizient den Iterator zu finden, der auf das gesuchte Element zeigt. Wenn der gefundene Wert nicht mit val übereinstimmt, wird der end()-Iterator zurückgegeben.

Alternative Lösungen

Eine andere Option ist die Verwendung eines std::set, das garantiert Elementreihenfolge und stellt eine find(T-Taste)-Methode bereit, die einen Iterator für das angegebene Element zurückgibt. Dies ist jedoch möglicherweise nicht für Fälle geeignet, in denen doppelte Elemente erforderlich sind.

Das obige ist der detaillierte Inhalt vonWie finde ich einen Elementindex mit der binären Suche in C?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!