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.
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.
low, high = 0, len(values) - 1📖 Die Seiten, die du noch durchsuchen musstmiddle = (low + high) // 2👆 In der Mitte aufschlagenlow = middle + 1➡️ Das Wort kommt später: erste Hälfte weghigh = middle - 1⬅️ Das Wort kommt früher: zweite Hälfte wegDie 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
lowundhighmarkieren den Teil der Liste, der das Ziel noch enthalten kann.middle = (low + high) // 2wählt den mittleren Index dieses Teils.- Ist
values[middle] < target, liegt das Ziel rechts, alsolow = middle + 1; sonsthigh = middle - 1. while low <= high:endet, wenn der Bereich leer ist, und die Funktion gibt dann-1zurück: nicht gefunden.- 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:
inoder 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
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))
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.
- Teste mit einer leeren Liste, einer Liste mit nur einem Element und einer Liste mit doppelten Werten.
- Gib den Zustand nach jedem Schritt aus, um den Algorithmus bei der Arbeit zu beobachten.
- Miss die Laufzeit mit 100, 1.000 und 10.000 Elementen und vergleiche sie mit einer anderen Lösung.
Häufige Fehler
< statt <= in der Schleife
Mit low < high wird ein Ziel an der letzten verbleibenden Position nie geprüft.
while low < high:
while low <= high:
An der Mitte hängen bleiben
Mit low = middle kann die Schleife endlos dieselbe Mitte prüfen.
low = middle
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.
- Fertigungszeit in der Fabrik Finde den frühesten Zeitpunkt, zu dem parallele Maschinen eine Zielanzahl von Produkten fertigstellen können. Mittel
- Median of Two Sorted Arrays Find the median of two sorted lists combined. Schwierig