binaere-suche

Binäre Suche

Kurz: Die binäre Suche findet ein Element in einer sortierten Liste, indem sie den Suchbereich immer wieder halbiert – statt alle Elemente einzeln zu prüfen.

Genauer: Sie vergleicht den gesuchten Wert mit dem mittleren Element: Ist er kleiner, geht es links weiter, ist er größer, rechts. Dadurch braucht sie bei n Elementen nur etwa log₂(n) Schritte – bei einer Million Elementen höchstens 20 (Laufzeit O(log n), siehe Big-O-Notation). Voraussetzung ist eine sortierte Datenmenge mit Indexzugriff.

Im Detail

def binaere_suche(liste, ziel):
    links, rechts = 0, len(liste) - 1
    while links <= rechts:
        mitte = (links + rechts) // 2
        if liste[mitte] == ziel:
            return mitte
        if liste[mitte] < ziel:
            links = mitte + 1
        else:
            rechts = mitte - 1
    return -1
 
zahlen = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binaere_suche(zahlen, 23))   # 5
print(binaere_suche(zahlen, 7))    # -1

Ablauf an einem Beispiel

Gesucht: 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Mitte = 16 (< 23) → rechte Hälfte [23, 38, 56, 72, 91]; Mitte = 56 (> 23) → [23, 38]; Mitte = 23 – gefunden.

Typische Fehler

• Überlauf bei (links + rechts) / 2 in Sprachen mit festen Ganzzahlen: besser links + (rechts - links) / 2.
• Endlosschleife durch falsche Grenzen (mitte statt mitte + 1).
• Anwendung auf unsortierte Daten – das Ergebnis ist dann beliebig.

Fertige Umsetzungen: bisect in Python, Arrays.binarySearch in Java, std::binary_search in C++, slices.BinarySearch in Go. Das Prinzip „Suchbereich halbieren“ steckt auch in Suchbäumen (Baum) und in git bisect.

Siehe auch: Algorithmen, Sortieren, Big-O-Notation, Array-Index