Wo ist Rechnung 1015?
In der Buchhaltung liegen 50.000 Rechnungen im System. Eine Kollegin fragt nach der Rechnung mit der Nummer 1015.
Das Programm kann auf zwei Arten suchen. Die eine ist einfach, die andere ist viel schneller, braucht aber Ordnung. Diese Lektion zeigt beide.
Am Ende dieser Lektion
Notiz
Ich kann einen Eintrag mit linearer und mit binärer Suche finden.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Algorithmus | eine feste Folge von Schritten für eine Aufgabe | |
| Lineare Suche | Einträge der Reihe nach prüfen, bis einer passt | |
| Binäre Suche | in einer sortierten Liste immer die Hälfte ausschließen | |
| Sortiert | geordnet, etwa aufsteigend nach Zahl | [3, 8, 15] |
| Treffer | der gesuchte Eintrag, den die Suche findet |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Die lineare Suche prüft einen nach dem anderen
Die einfachste Suche beginnt vorn. Sie vergleicht jeden Eintrag mit dem gesuchten. Passt einer, ist die Suche zu Ende.
Das klappt bei jeder Liste, auch bei einer unsortierten. Im schlechtesten Fall prüfen Sie aber alle Einträge.
Probieren Sie es: lineare Suche
# Lineare Suche: von vorn, Eintrag für Eintrag.
rechnungen = [1042, 1007, 1093, 1015, 1088]
gesucht = 1015
gefunden = -1 # -1 heißt: nicht gefunden
for stelle in range(len(rechnungen)):
if rechnungen[stelle] == gesucht:
gefunden = stelle
break # aufhören, sobald es gefunden ist
print("Gefunden an Stelle:", gefunden)
# Suchen Sie jetzt 1099. Was zeigt das Programm?
Die binäre Suche halbiert den Rest
Ist die Liste sortiert, geht es klüger. Sie schauen auf den Eintrag in der Mitte. Ist er zu klein, liegt der gesuchte in der rechten Hälfte. Ist er zu groß, in der linken.
Die falsche Hälfte fällt weg. Dann wiederholen Sie das mit dem Rest, bis Sie ihn haben oder nichts mehr übrig ist.
Beispiel: 34 in sieben Nummern suchen
| Schritt | Noch im Rennen | Mitte | Vergleich |
|---|---|---|---|
| 1 | 3, 8, 15, 21, 34, 40, 57 | 21 | 34 ist größer: rechte Hälfte |
| 2 | 34, 40, 57 | 40 | 34 ist kleiner: linke Hälfte |
| 3 | 34 | 34 | Treffer |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Probieren Sie es: binäre Suche
# Binäre Suche: die Liste muss sortiert sein.
nummern = [3, 8, 15, 21, 34, 40, 57]
gesucht = 34
links = 0
rechts = len(nummern) - 1
schritte = 0
while links <= rechts:
mitte = (links + rechts) // 2
schritte = schritte + 1
if nummern[mitte] == gesucht:
print("Gefunden an Stelle", mitte, "nach", schritte, "Schritten")
break
if nummern[mitte] < gesucht:
links = mitte + 1 # die linke Hälfte kann weg
else:
rechts = mitte - 1 # die rechte Hälfte kann weg
# Suchen Sie 3 statt 34 und vergleichen Sie die Schritte.
Ein häufiger Fehler
Warnung
Viele denken, die binäre Suche sei immer besser. Sie funktioniert aber nur in einer sortierten Liste. In einer unsortierten Liste kann sie den Eintrag übersehen, ohne eine Fehlermeldung zu zeigen. Sortieren Sie erst, oder nehmen Sie die lineare Suche.
Beispiel: Vergleiche im schlechtesten Fall
| Einträge | Lineare Suche | Binäre Suche |
|---|---|---|
| 7 | 7 | 3 |
| 1000 | 1000 | 10 |
| 1.000.000 | 1.000.000 | 20 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.