Eine Million Einträge in zwanzig Schritten durchsuchen
Die binäre Suche findet einen Wert in einer sortierten Liste mit einer Million Einträgen in höchstens 20 Vergleichen. Die lineare Suche braucht im schlimmsten Fall eine Million.
Ein Rathaus sucht in einer Liste aller Postleitzahlen den passenden Ort. Wie viele Schritte das kostet, hängt von der Suchmethode ab, nicht vom Rechner.
Am Ende dieser Lektion
Notiz
Ich kann die lineare und die binäre Suche vergleichen und die Schritte beider zählen.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Lineare Suche | ein Element nach dem anderen prüfen | |
| Binäre Suche | die Mitte prüfen und eine Hälfte verwerfen | |
| Sortiert | nach einer festen Reihenfolge geordnet | 3, 8, 15, 22 |
| Schlimmster Fall | die Eingabe, bei der ein Algorithmus am meisten Schritte braucht | |
| Halbieren | die Menge der Kandidaten auf die Hälfte verkleinern |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Lineare Suche prüft Wert für Wert
Die lineare Suche beginnt vorn und vergleicht jeden Wert mit dem Ziel. Sie hört auf, wenn sie das Ziel findet oder die Liste endet.
Im besten Fall steht das Ziel vorn und es ist ein Schritt. Im schlimmsten Fall steht es hinten oder fehlt, und es sind n Schritte. Die Liste muss dafür nicht sortiert sein.
Beide Suchen im Vergleich
# Postleitzahlen, aufsteigend sortiert.
plz = [10115, 20095, 30159, 40213, 50667, 60311, 70173, 80331, 90402, 99084]
ziel = 80331
# Lineare Suche: von vorn, bis der Wert kommt.
schritte = 0
for i in range(len(plz)):
schritte = schritte + 1
if plz[i] == ziel:
break
print("linear: Stelle", i, "nach", schritte, "Schritten")
# Binaere Suche: die Mitte pruefen, dann eine Haelfte wegwerfen.
unten = 0
oben = len(plz) - 1
schritte = 0
while unten <= oben:
mitte = (unten + oben) // 2
schritte = schritte + 1
if plz[mitte] == ziel:
print("binaer: Stelle", mitte, "nach", schritte, "Schritten")
break
elif plz[mitte] < ziel:
unten = mitte + 1
else:
oben = mitte - 1
# Aendern Sie ziel auf 10115, dann auf 99084, dann auf 70000.
Binäre Suche halbiert in jedem Schritt
Die binäre Suche prüft den Wert in der Mitte. Ist das Ziel kleiner, kann es nur links stehen. Ist es größer, nur rechts.
So fällt in jedem Schritt die Hälfte der Kandidaten weg. Sie führt zwei Grenzen mit, unten und oben, und endet, wenn unten hinter oben liegt.
Eine Suche nach 70000, die nichts findet
| Runde | unten | oben | Mitte | Wert in der Mitte | Entscheidung |
|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 50667 | zu klein: unten wird 5 |
| 2 | 5 | 9 | 7 | 80331 | zu groß: oben wird 6 |
| 3 | 5 | 6 | 5 | 60311 | zu klein: unten wird 6 |
| 4 | 6 | 6 | 6 | 70173 | zu groß: oben wird 5 |
| Ende | 6 | 5 | unten liegt hinter oben: nicht enthalten |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Die Schritte im schlimmsten Fall
| Einträge n | Lineare Suche | Binäre Suche |
|---|---|---|
| 10 | 10 | 4 |
| 100 | 100 | 7 |
| 1000 | 1000 | 10 |
| 1.000.000 | 1.000.000 | 20 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Die binäre Suche braucht eine sortierte Liste
Der Gedanke "links ist kleiner, rechts ist größer" stimmt nur in einer sortierten Liste. In einer ungeordneten Liste wirft die Suche die falsche Hälfte weg und übersieht Werte.
Sortiert hängt auch von der Ordnung ab. Als Text steht 100 vor 9, als Zahl dahinter. Die Befehle zeigen beide Ordnungen und eine lineare Suche in einer Datei.
Die falsche Hälfte wird weggeworfen
# Die binaere Suche setzt eine sortierte Liste voraus.
zahlen = [40, 10, 30, 20, 50]
ziel = 10
unten = 0
oben = len(zahlen) - 1
gefunden = False
while unten <= oben:
mitte = (unten + oben) // 2
if zahlen[mitte] == ziel:
gefunden = True
break
elif zahlen[mitte] < ziel:
unten = mitte + 1
else:
oben = mitte - 1
print("gefunden:", gefunden)
# Die 10 steht in der Liste. Sortieren Sie die Liste von Hand und fuehren Sie erneut aus.
Zahlen als Text sortieren
printf "10\n9\n100\n" | sortHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Zahlen als Zahlen sortieren
printf "10\n9\n100\n" | sort -nHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Lineare Suche nach der Zeile 640
seq 1 1000 | grep -n -x 640Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Ein häufiger Fehler
Warnung
Viele denken, die binäre Suche sei immer besser. Sie setzt aber eine sortierte Liste voraus. Muss man erst sortieren und sucht nur einmal, ist die lineare Suche meist billiger. Die binäre Suche lohnt sich, wenn man oft in derselben sortierten Liste sucht.
Weiterführend
Wie viele Schritte braucht die binäre Suche höchstens bei 2000 Einträgen? Bei 4000? Schreiben Sie die Zahlen auf und erklären Sie das Muster.
Prüfen Sie Ihre Antwort mit python3 -c "print((2000).bit_length(), (4000).bit_length())" im Lab.