Was ist eine binäre Suche?

Die in diesem Blog verfassten Artikel wurden mit dem Ziel erstellt, zu unterrichten. Außerdem können die Informationen im Artikel falsch sein, also seien Sie bitte vorsichtig.

Die binäre Suche prüft den Mittelwert des sortierten Bereichs und reduziert das Suchintervall um die Hälfte.

1 3 5 7 9 11 13
↑ 7 OK

Um 11 zu finden, lassen Sie nur die rechte Hälfte übrig.

Standardimplementierung

int BinarySearch(const std::vector<int>& Values, int Target)
{
    int Left = 0;
    int Right = static_cast<int>(Values.size()) - 1;

    while (Left <= Right)
    {
        const int Middle = Left + (Right - Left) / 2;

        if (Values[Middle] == Target)
        {
            return Middle;
        }

        if (Values[Middle] < Target)
        {
            Left = Middle + 1;
        }
        else
        {
            Right = Middle - 1;
        }
    }

    return -1;
}

Da sich die Reichweite jedes Mal halbiert, beträgt die ZeitkomplexitätO(log N)Bin.

Muss sortiert werden

Wenn die binäre Suche auf unsortierte Daten angewendet wird, ist es unmöglich zu bestimmen, welche Hälfte verworfen werden kann. Wenn Sie bei jeder Suche zuerst sortieren, müssen Sie auch die Sortierkosten berechnen.

Die Randbedingungen für den ersten gleichen Wert, den letzten gleichen Wert und die Ermittlung der Position des Werts unterscheiden sich geringfügig. In C++std::lower_boundUndstd::upper_boundSie können diese Grenze sicher erhalten, indem Sie verwenden.

Der schwierige Teil der binären Suche besteht darin, nicht den Mittelwert zu finden. Unabhängig davon, ob es sich bei dem aktuellen Bereich um einen geschlossenen oder einen halboffenen Abschnitt handelt, gilt bis zum Ende dieselbe Regel.