Ein Lied in 2000 Liedern finden
Eine Suche findet ein Element in einer Liste. Es gibt zwei Wege: die lineare Suche und die binäre Suche. Bei 1000 Einträgen braucht die zweite höchstens 10 Schritte statt bis zu 1000.
Deine Playlist hat 2000 Lieder, und du willst ein bestimmtes finden. Du kannst jedes der Reihe nach ansehen. Oder du nutzt aus, dass die Liste geordnet ist.
Am Ende dieser Lektion
Notiz
Ich kann ein Element mit der linearen und der binären Suche finden.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Algorithmus | eine Folge von Schritten, die ein Problem löst | |
| Lineare Suche | jedes Element der Reihe nach ansehen | |
| Binäre Suche | in die Mitte schauen und eine Hälfte wegwerfen | |
| Sortiert | in einer Reihenfolge, zum Beispiel von klein nach groß | |
| Index | die Stelle eines Elements in einer Liste, die erste ist 0 | liste[0] |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Die lineare Suche sieht jedes Element an
Die lineare Suche beginnt vorn. Sie vergleicht das erste Element mit dem Ziel, dann das zweite und so weiter. Sie hört auf, sobald sie das Ziel hat.
Sie funktioniert immer, auch wenn die Liste durcheinander ist. Im schlimmsten Fall sieht sie jedes Element an, also so viele Schritte, wie die Liste lang ist.
Beispiel: die 9 in einer kurzen Liste suchen
| Schritt | Stelle | Element | Ist es die 9? |
|---|---|---|---|
| 1 | 0 | 7 | Nein, weiter |
| 2 | 1 | 3 | Nein, weiter |
| 3 | 2 | 9 | Ja, gefunden nach 3 Schritten |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Probiere es: ändere das Ziel
liste = [7, 3, 9, 4, 6]
ziel = 9 # Ändere das Ziel auf 6 und lies die Zahl der Schritte.
schritte = 0
stelle = -1
for i in range(len(liste)):
schritte = schritte + 1
if liste[i] == ziel:
stelle = i
break # Gefunden: weiter suchen wäre Zeitverschwendung.
print("Stelle:", stelle, "nach", schritte, "Schritten")
Die binäre Suche halbiert den Suchbereich
Die binäre Suche braucht eine sortierte Liste. Sie schaut in die Mitte. Ist das Element dort kleiner als das Ziel, liegt das Ziel rechts, und die linke Hälfte kann weg. Ist es größer, kann die rechte Hälfte weg.
Das wiederholt sie mit dem Rest, bis sie das Ziel findet oder nichts mehr übrig ist.
Beispiel: die 34 in neun sortierten Zahlen
| Schritt | Bereich (Stellen) | Mitte | Element in der Mitte | Was folgt |
|---|---|---|---|---|
| 1 | 0 bis 8 | 4 | 21 | Kleiner als 34: die linke Hälfte fällt weg |
| 2 | 5 bis 8 | 6 | 34 | Gefunden nach 2 Schritten |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Die binäre Suche in Python
liste = [3, 8, 12, 15, 21, 27, 34, 40, 46]
ziel = 34 # Ändere das Ziel auf 3 und lies die Zahl der Schritte.
links = 0
rechts = len(liste) - 1
schritte = 0
stelle = -1
while links <= rechts:
mitte = (links + rechts) // 2
schritte = schritte + 1
if liste[mitte] == ziel:
stelle = mitte
break
if liste[mitte] < ziel:
links = mitte + 1 # Das Ziel liegt rechts.
else:
rechts = mitte - 1 # Das Ziel liegt links.
print("Stelle:", stelle, "nach", schritte, "Schritten")
Ein häufiger Fehler
Warnung
Viele denken, die binäre Suche sei immer besser. Sie findet aber in einer durcheinander liegenden Liste das Falsche, weil das Wegwerfen einer Hälfte nur bei sortierten Daten stimmt. Ist die Liste nicht sortiert, nimm die lineare Suche oder sortiere zuerst.
Bevor du anfängst
Notiz
Drück oben in der Leiste auf Lab starten und warte, bis JupyterLab läuft. Jede Schaltfläche Ausführen tippt ihren Befehl in das Terminal neben dem Lab. Jeder Befehl startet Python im Container jupyter.
Die Zeilen der Datei hires.csv zählen
docker exec jupyter python3 -c "print(len(open('hires.csv').readlines()) - 1)"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Wie viele Schritte bis zum ersten Regentag?
Die Datei hires.csv hat eine Zeile für jeden Tag des Jahres 2025, also 365 Tage mit dem Wetter. Der nächste Befehl sucht linear den ersten Tag mit dem Wetter „rainy“ (Regen). Er gibt die Zahl der Schritte aus.
Linear nach dem ersten Regentag suchen
docker exec jupyter python3 -c "print([z.split(',')[3] for z in open('hires.csv')][1:].index('rainy') + 1)"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Die binäre Suche im Lab ausführen
Die Tage des Jahres haben die Nummern 1 bis 365 und sind sortiert. Der erste Befehl schreibt die binäre Suche in die Datei suche.py und gibt nichts aus. Der zweite startet sie. Sie sucht den Tag 250.
Die Datei suche.py schreiben
docker exec jupyter sh -c "printf 'tage = list(range(1, 366))\nziel = 250\nlinks = 0\nrechts = len(tage) - 1\nschritte = 0\nwhile links <= rechts:\n mitte = (links + rechts) // 2\n schritte = schritte + 1\n if tage[mitte] == ziel:\n break\n if tage[mitte] < ziel:\n links = mitte + 1\n else:\n rechts = mitte - 1\nprint(\"Tag\", ziel, \"nach\", schritte, \"Schritten\")\n' > suche.py"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Die binäre Suche starten
docker exec jupyter python3 suche.pyHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Wie viele Schritte brauchen beide höchstens?
Die lineare Suche braucht bis zu n Schritte bei n Elementen. Die binäre Suche halbiert den Bereich, also zählt sie nur, wie oft man n halbieren kann, bis nichts mehr übrig ist.
Verdoppelst du die Liste, kommt bei der binären Suche nur ein Schritt dazu.
Schritte im ungünstigsten Fall
| Elemente | Lineare Suche | Binäre Suche |
|---|---|---|
| 8 | 8 | 4 |
| 100 | 100 | 7 |
| 1000 | 1000 | 10 |
| eine Million | eine Million | 20 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Die Schritte der binären Suche nachrechnen
docker exec jupyter python3 -c "print([n.bit_length() for n in [8, 100, 1000, 1000000]])"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Weiterführend: nicht gefunden
Was gibt deine binäre Suche zurück, wenn das Ziel nicht in der Liste steht? Suche in der Datei suche.py nach 400 statt 250. Wie viele Schritte braucht sie, bis sie aufgibt? Überlege vorher und rechne dann nach.