Wie implementiert man einen iteratorbasierten binären Suchalgorithmus für sortierte C-Container?

Binärer Suchalgorithmus mit Iterator-Rückgabe für C-Container

Der std::binary_search-Algorithmus des STL identifiziert effizient das Vorhandensein eines Elements innerhalb einer Sortierung Container, aber es wird nur ein boolescher Wert zurückgegeben. Für Szenarien, in denen die genaue Position des Elements entscheidend ist, benötigen Sie möglicherweise einen Iterator-basierten Suchalgorithmus.

Um diesem Bedarf gerecht zu werden, kann der folgende benutzerdefinierte binäre Suchalgorithmus eingesetzt werden:

<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 den Einfügepunkt des Werts im Container zu finden (falls er eingefügt werden sollte). Wenn der Wert vorhanden ist, wird der Iterator zurückgegeben; andernfalls wird der Enditerator zurückgegeben. Dieser Ansatz gewährleistet sowohl Geschwindigkeit als auch Präzision

Sie können auch die Verwendung eines std::set in Betracht ziehen, das eine Iterator-Suchfunktion (T-Taste) bereitstellt, die den Iterator, der auf das angegebene Element zeigt, direkt 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 implementiert man einen iteratorbasierten binären Suchalgorithmus für sortierte C-Container?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!