Binäre Suche

Die binäre Suche findet einen Wert in einer sortierten Liste, ohne alle Einträge anzusehen. Sie schaut in die Mitte, entscheidet anhand des Vergleichs, in welcher Hälfte der Wert liegen kann, und wirft die andere Hälfte weg.

Genau so sucht man einen Namen im Telefonbuch: aufschlagen, vergleichen, vorne oder hinten weitersuchen. Bei einer Million Einträgen genügen zwanzig Vergleiche.

Der Suchbereich wird durch zwei Grenzen beschrieben, low und high. Solange er mindestens ein Element enthält, wiederholt sich:

1. Bestimme die Mitte des aktuellen Bereichs.
2. Ist der Wert dort der gesuchte, ist die Suche zu Ende.
3. Ist er kleiner als der gesuchte Wert, kann das Gesuchte nur rechts liegen, also wandert low hinter die Mitte.
4. Andernfalls wandert high vor die Mitte.

Kreuzen sich die Grenzen, ist der Bereich leer und der Wert kommt nicht vor.

Weil sich der Bereich in jedem Schritt halbiert, sind es höchstens log₂ n Schritte: 10 Schritte für 1.000 Werte, 20 für eine Million, 30 für eine Milliarde.

public static class BinarySearch
{
    // Liefert den Index des Werts im sortierten Array, oder -1, wenn er nicht vorkommt.
    public static int IndexOf(int[] sortedNumbers, int value)
    {
        var low = 0;
        var high = sortedNumbers.Length - 1;

        // Läuft, solange das Suchfenster noch mindestens ein Element enthält.
        while (low <= high)
        {
            // So geschrieben statt (low + high) / 2, damit nichts überlaufen kann.
            var middle = low + (high - low) / 2;
            var current = sortedNumbers[middle];

            if (current == value)
                return middle;

            // Das Array ist sortiert, der Wert kann also nur in einer der beiden Hälften liegen.
            // Die andere Hälfte fällt weg, das Fenster halbiert sich mit jedem Schritt.
            if (current < value)
                low = middle + 1;
            else
                high = middle - 1;
        }

        return -1;
    }
}

// Das Array muss sortiert sein - genau davon lebt der Algorithmus.
var numbers = new[] { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 };

Console.WriteLine(BinarySearch.IndexOf(numbers, 23));
Console.WriteLine(BinarySearch.IndexOf(numbers, 42));

5
-1

• Die Liste muss sortiert sein. Ist sie es nicht, liefert der Algorithmus falsche Ergebnisse, ohne es zu merken.
• Die Mitte wird als low + (high - low) / 2 berechnet und nicht als (low + high) / 2. Bei sehr großen Indizes könnte die Summe sonst überlaufen. Dieser Fehler steckte jahrelang in gängigen Bibliotheken.
• .NET bringt das fertig mit: Array.BinarySearch. Der Rückgabewert ist dort bei einem Treffer der Index, sonst das bitweise Komplement der Einfügeposition.