Suchalgorithmen: Lineare und binäre Suche verstehen

Stell dir vor, du suchst in einem Telefonbuch nach einem Namen. Würdest du wirklich auf Seite 1 anfangen und jede Zeile einzeln durchgehen? Vermutlich nicht – du schlägst irgendwo in der Mitte auf und grenzt den Bereich Schritt für Schritt ein. Genau dieser Unterschied steckt hinter den beiden wichtigsten Suchalgorithmen der Informatik: der linearen und der binären Suche. In diesem Beitrag schauen wir uns beide mit lauffähigem Python-Code an, vergleichen ihre Laufzeit und am Ende verstehst du, warum die Wahl des richtigen Verfahrens über Millisekunden oder Minuten entscheidet.

Das Problem: ein Element in vielen finden

Suchen ist eine der häufigsten Aufgaben überhaupt: ein Benutzer in einer Datenbank, ein Produkt im Warenkorb, ein Wert in einer Messreihe. Die Frage ist immer dieselbe – an welcher Stelle steckt das gesuchte Element, und gibt es das überhaupt? Wie schnell wir eine Antwort bekommen, hängt entscheidend davon ab, ob unsere Daten sortiert sind oder nicht. Diese eine Eigenschaft entscheidet darüber, welcher Algorithmus überhaupt infrage kommt.

Lineare Suche: einfach, aber gründlich

Die lineare Suche ist der naheliegendste Ansatz: Du gehst die Liste von vorne nach hinten durch und vergleichst jedes Element mit deinem Ziel. Findest du es, gibst du die Position zurück – sonst meldest du -1, also „nicht gefunden“.

def lineare_suche(daten, ziel):
    for index, wert in enumerate(daten):
        if wert == ziel:
            return index
    return -1

zahlen = [4, 8, 15, 16, 23, 42]
print(lineare_suche(zahlen, 23))  # 4
print(lineare_suche(zahlen, 99))  # -1

Der große Vorteil: Die Daten müssen nicht sortiert sein. Der Nachteil zeigt sich bei großen Mengen. Liegt das gesuchte Element ganz hinten – oder gar nicht in der Liste –, musst du jedes einzelne Element anfassen. Bei einer Million Einträgen sind das im schlechtesten Fall eine Million Vergleiche. In der Sprache der Big-O-Notation ist das eine Laufzeit von O(n): Der Aufwand wächst linear mit der Datenmenge.

Binäre Suche: teile und herrsche

Wenn die Daten bereits sortiert sind, geht es deutlich schlauer. Die binäre Suche schaut sich das Element in der Mitte an. Ist es zu klein, kann das Ziel nur rechts davon liegen – die gesamte linke Hälfte fällt weg. Ist es zu groß, fällt die rechte Hälfte weg. Mit jedem Vergleich halbierst du den Suchbereich.

def binaere_suche(daten, ziel):
    links, rechts = 0, len(daten) - 1
    while links <= rechts:
        mitte = (links + rechts) // 2
        if daten[mitte] == ziel:
            return mitte
        elif daten[mitte] < ziel:
            links = mitte + 1   # rechte Hälfte weiter durchsuchen
        else:
            rechts = mitte - 1  # linke Hälfte weiter durchsuchen
    return -1

zahlen = [4, 8, 15, 16, 23, 42]
print(binaere_suche(zahlen, 23))  # 4

Der Trick steckt in den beiden Zeigern links und rechts, die den noch zu durchsuchenden Bereich markieren. Solange sich beide nicht überholt haben (links <= rechts), gibt es noch etwas zu prüfen. Wichtig: Funktioniert nur auf sortierten Daten – sonst sind die Schlussfolgerungen „links“ und „rechts“ schlicht falsch.

Die rekursive Variante

Binäre Suche lässt sich auch elegant rekursiv formulieren: Statt einer Schleife ruft die Funktion sich selbst mit einem kleineren Bereich auf. Das ist ein schönes Beispiel dafür, wie sich ein Problem in immer kleinere Teilprobleme zerlegen lässt.

def binaere_suche_rekursiv(daten, ziel, links=0, rechts=None):
    if rechts is None:
        rechts = len(daten) - 1
    if links > rechts:          # Bereich ist leer -> nicht gefunden
        return -1
    mitte = (links + rechts) // 2
    if daten[mitte] == ziel:
        return mitte
    elif daten[mitte] < ziel:
        return binaere_suche_rekursiv(daten, ziel, mitte + 1, rechts)
    else:
        return binaere_suche_rekursiv(daten, ziel, links, mitte - 1)

print(binaere_suche_rekursiv([4, 8, 15, 16, 23, 42], 16))  # 3

Beide Varianten liefern dasselbe Ergebnis. Die iterative Version kommt ohne zusätzlichen Speicher für den Aufruf-Stack aus, die rekursive ist dafür oft näher an der gedanklichen Beschreibung „teile und herrsche“.

Der große Unterschied: O(n) gegen O(log n)

Warum lohnt sich der Aufwand? Weil das Halbieren extrem schnell zum Ziel führt. Bei jedem Schritt verschwindet die Hälfte der Kandidaten. Aus einer Million werden 500.000, dann 250.000, dann 125.000 – nach rund 20 Schritten bleibt nur noch ein Element übrig. Das ist die Laufzeit O(log n). Folgendes kleine Skript macht den Unterschied greifbar:

import math

for n in [10, 1_000, 1_000_000]:
    schritte_binaer = math.ceil(math.log2(n))
    print(f"{n:>9} Eintraege: linear bis {n}, binaer ca. {schritte_binaer} Schritte")

# 10 Eintraege: linear bis 10, binaer ca. 4 Schritte
# 1000 Eintraege: linear bis 1000, binaer ca. 10 Schritte
# 1000000 Eintraege: linear bis 1000000, binaer ca. 20 Schritte

Eine Million gegen zwanzig – das ist kein kleiner Vorteil, sondern ein Unterschied von Faktor 50.000. Die Entscheidung zwischen den beiden Verfahren hängt von einer einzigen Frage ab:

• Unsortierte Daten oder nur einmal gesucht? Lineare Suche reicht – Sortieren würde sich nicht lohnen.
• Sortierte Daten und viele Suchanfragen? Binäre Suche, jedes Mal.

In der Praxis: das bisect-Modul

Du musst die binäre Suche im Alltag nicht selbst schreiben – Python bringt sie im Standardmodul bisect schon mit, sauber implementiert und getestet. Das Modul findet nicht nur Positionen, sondern hilft auch dabei, eine Liste sortiert zu halten:

import bisect

zahlen = [4, 8, 15, 16, 23, 42]

# Position des Werts finden
pos = bisect.bisect_left(zahlen, 23)
if pos < len(zahlen) and zahlen[pos] == 23:
    print(f"Gefunden an Index {pos}")  # Gefunden an Index 4

# Neuen Wert einfuegen, ohne die Sortierung zu zerstoeren
bisect.insort(zahlen, 19)
print(zahlen)  # [4, 8, 15, 16, 19, 23, 42]

Selbst implementieren solltest du den Algorithmus trotzdem einmal – nicht, weil du musst, sondern weil du das Prinzip dahinter danach nie wieder vergisst.

Fazit

Die lineare Suche ist einfach und funktioniert immer, zahlt das aber bei großen Datenmengen mit langer Laufzeit. Die binäre Suche ist dramatisch schneller, verlangt dafür aber sortierte Daten. Der entscheidende Gedanke: Ein guter Algorithmus ersetzt rohe Rechenkraft durch clevere Struktur. Wenn du das nächste Mal eine Liste durchsuchst, frag dich kurz, ob sie sortiert ist – diese eine Frage kann aus einer Million Schritten zwanzig machen. Als nächsten Schritt lohnt sich ein Blick auf Datenstrukturen wie Hash-Tabellen, die das Suchen unter idealen Bedingungen sogar auf nahezu konstante Zeit drücken.