Binärsuche: schnell in sortierten Daten finden

Kurz: Die Binärsuche halbiert in jedem Schritt den Suchbereich einer sortierten Liste und braucht dadurch nur logarithmisch viele Vergleiche statt linear vieler.

Genauer: Wie beim Raten einer Zahl zwischen 1 und 100 („größer/kleiner?“): Immer in die Mitte schauen, dann die falsche Hälfte wegwerfen. Voraussetzung: Die Daten sind sortiert und der Zugriff auf beliebige Position ist schnell (Array).

Im Detail

Idee und Ablauf

1. links = 0, rechts = n − 1.
2. mitte = links + (rechts − links) / 2.
3. Ist a[mitte] == ziel → gefunden. Ist a[mitte] < ziel → links = mitte + 1, sonst rechts = mitte − 1.
4. Wiederholen, bis links > rechts (nicht gefunden). Beispiel: Suche 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]: Mitte 16 < 23 → rechte Hälfte; Mitte 56 > 23 → links; Mitte 23 → gefunden nach 3 Schritten.

Code

def binaersuche(a, ziel):
    links, rechts = 0, len(a) - 1
    while links <= rechts:
        mitte = links + (rechts - links) // 2   # vermeidet Überlauf
        if a[mitte] == ziel:
            return mitte
        if a[mitte] < ziel:
            links = mitte + 1
        else:
            rechts = mitte - 1
    return -1

In Python: Modul bisect (bisect_left), in Java Arrays.binarySearch, JavaScript manuell, C++ std::binary_search/lower_bound. Typische Fehler: Off-by-one bei den Grenzen, Überlauf bei (l + r) / 2 in festen Integer-Typen, Endlosschleifen durch falsche Grenzänderung, unsortierte Daten.

Laufzeit

Pro Schritt halbiert sich der Bereich: höchstens ⌈log₂ n⌉ + 1 Vergleiche. 1 Million Einträge: ≈ 20 Vergleiche; 1 Milliarde: ≈ 30. Die lineare Suche braucht im Mittel n/2. Aufwand: O(log n). Aber: Sortieren kostet O(n log n); lohnt sich, wenn oft gesucht wird. Bei Listen (verkettet) bringt Binärsuche nichts (kein Direktzugriff), dafür Suchbäume/B-Bäume/Indizes.

Varianten und Anwendungen

• Untere/obere Schranke (erste/letzte Position eines Werts, Einfügeposition).
• Binärsuche auf der Antwort: „kleinste Kapazität, sodass Lieferung in 5 Tagen klappt“ (Monotonie nutzen).
• Wurzel/Nullstelle (Bisektionsverfahren).
• git bisect: findet den fehlerhaften Commit in log₂(n) Schritten.
• Datenbank-Indizes, Telefonbuch, Wörterbuch, Sortierte Dateien, Autovervollständigung.
• Prüfungs-Tipp (IHK): Schrittzahl für n Elemente herleiten (2^k ≥ n).

Siehe auch: Big-O-Notation, Sortieren, B-Baum