Binäre Suche in Python
Die binäre Suche halbiert den verbleibenden Suchbereich nach jedem Vergleich.
Was ist Binäre Suche?
Die binäre Suche halbiert den verbleibenden Suchbereich nach jedem Vergleich.
Finde einen Wert effizient in einer sortierten Liste.
Wann wird dieser Ansatz verwendet?
- Algorithmen und Datenstrukturen anhand von ausführbarem Code verstehen.
- Die einzelnen Verarbeitungsschritte und Randfälle nachvollziehen.
- Laufzeit und Speicherbedarf verschiedener Lösungswege vergleichen.
Binäre Suche in Python visualisieren
O(log n)Mit Start oder Schritt kannst du jeden Vergleich und jede Datenbewegung verfolgen.
Beispielcode
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))Erwartete Ausgabe
3So funktioniert es
Der mittlere Wert entscheidet, ob links oder rechts weitergesucht wird. Die Laufzeit beträgt O(log n); die Eingabe muss sortiert sein.
Ändere die Werte und führe das Programm im CodeUtility Python Online-Compiler aus, ohne Python lokal zu installieren.
Übungsaufgaben
Verändere Eingaben und Randfälle, bevor du die Lösung mit größeren Datenmengen testest.
- Teste leere Eingaben, ein Element und doppelte Werte.
- Gib den Zustand nach jedem Schritt aus.
- Vergleiche Laufzeit und Speicherbedarf mit einem alternativen Verfahren.