Python-Algorithmen

Binäre Suche (binary search) in Python

In dieser Lektion implementierst du die binäre Suche, um einen Wert in einer sortierten Liste schnell zu finden.

  • Fortgeschritten
  • 2 Min. Lesezeit
  • 1 ausführbares Beispiel

Einführung

Das Problem

Wenn du einen Wert in einer Liste mit einer Million Einträgen suchst und jeden einzeln prüfst, brauchst du bis zu eine Million Vergleiche. Ist die Liste sortiert, geht es viel besser: Etwa 20 Vergleiche reichen, weil jeder Vergleich die Hälfte des Rests ausschließt.

Stell es dir so vor

Binäre Suche ist wie das Nachschlagen in einem gedruckten Wörterbuch. Du schlägst es in der Mitte auf, schaust, ob dein Wort davor oder danach kommt, und wirfst die Hälfte weg, in der es nicht stehen kann. Das wiederholst du mit der restlichen Hälfte, bis du bei deinem Wort landest.

Vom Wörterbuch zum Code
low, high = 0, len(values) - 1📖 Die Seiten, die du noch durchsuchen musst
middle = (low + high) // 2👆 In der Mitte aufschlagen
low = middle + 1➡️ Das Wort kommt später: erste Hälfte weg
high = middle - 1⬅️ Das Wort kommt früher: zweite Hälfte weg
Jeder Vergleich halbiert den Rest, deshalb brauchen selbst riesige Listen nur wenige Schritte.
In einem Satz

Die binäre Suche findet einen Wert in einer sortierten Liste, indem sie ihn immer wieder mit dem mittleren Element vergleicht und die Hälfte verwirft, in der er nicht sein kann. Sie braucht O(log n) Schritte.

Das Wichtigste

  1. low und high markieren den Teil der Liste, der das Ziel noch enthalten kann.
  2. middle = (low + high) // 2 wählt den mittleren Index dieses Teils.
  3. Ist values[middle] < target, liegt das Ziel rechts, also low = middle + 1; sonst high = middle - 1.
  4. while low <= high: endet, wenn der Bereich leer ist, und die Funktion gibt dann -1 zurück: nicht gefunden.
  5. Für 17 prüft die Suche 12, dann 25, dann 17: drei Vergleiche statt vier.

Wann verwendet man das?

  • Große sortierte Daten durchsuchen: IDs, Wörterbücher, sortierte Logs.
  • Die Stelle finden, an der ein Wert eingefügt werden muss, damit die Liste sortiert bleibt.
  • Ratespiele und alle Probleme, bei denen sich die Antwort mit größer oder kleiner eingrenzen lässt.

Wann du es nicht brauchst

  • Die Daten sind nicht sortiert: Nur für eine einzige Suche zu sortieren kostet mehr als eine lineare Suche.
  • Kleine Listen oder einmalige Suchen: in oder ein Dictionary ist einfacher. Suchst du oft nach einem Schlüssel, ist ein Dictionary oder Set sogar noch schneller.

Binäre Suche (binary search) in Python visualisieren

O(log n)

Mit Start oder Schritt kannst du jeden Vergleich und jede Datenbewegung verfolgen.

Beispielcode

Code ausführen →
main.py
def binary_search(values, target):
    low, high = 0, len(values) - 1
    while low <= high:
        middle = (low + high) // 2
        if values[middle] == target:
            return middle
        if values[middle] < target:
            low = middle + 1
        else:
            high = middle - 1
    return -1

print(binary_search([3, 8, 12, 17, 25, 31], 17))
Run-Button für dieses Beispiel erstellen

Ergebnis der Ausführung

3

Erklärung des Codes

Die Variablen low und high legen den noch zu durchsuchenden Bereich fest. Ist das mittlere Element kleiner als der gesuchte Wert, verwirft der Algorithmus mit low = middle + 1 die linke Hälfte, sonst die rechte. Die Zeitkomplexität ist O(log n), vorausgesetzt, die Eingabeliste ist bereits sortiert.

Ändere die Werte und führe das Programm im CodeUtility Python Online-Compiler aus, ohne Python lokal zu installieren.

Übungen zur Vertiefung

Ändere den Code anhand der folgenden Vorschläge. Wenn du selbst etwas änderst und das Ergebnis beobachtest, verstehst du viel mehr, als wenn du den Code nur liest.

  1. Teste mit einer leeren Liste, einer Liste mit nur einem Element und einer Liste mit doppelten Werten.
  2. Gib den Zustand nach jedem Schritt aus, um den Algorithmus bei der Arbeit zu beobachten.
  3. Miss die Laufzeit mit 100, 1.000 und 10.000 Elementen und vergleiche sie mit einer anderen Lösung.
Im Python-Compiler ausführen →

Häufige Fehler

< statt <= in der Schleife

Mit low < high wird ein Ziel an der letzten verbleibenden Position nie geprüft.

Problem
while low < high:
Lösung
while low <= high:

An der Mitte hängen bleiben

Mit low = middle kann die Schleife endlos dieselbe Mitte prüfen.

Problem
low = middle
Lösung
low = middle + 1

Lektion fertig?

Markiere sie als gelernt, um deinen Fortschritt zu verfolgen.

Mit einer Challenge üben

Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.

Alle Challenges