Lineare Suche (linear search) in Python
In dieser Lektion implementierst du die lineare Suche, um die Position eines Werts in einer Liste zu finden.
Was ist die lineare Suche?
Das Problem
Manchmal sind die Daten nicht sortiert, oder du suchst nur einmal darin: eine kurze Namensliste, die Bestellungen von heute, der erste Fehler in einem Log. Dann brauchst du die einfachste Suche, die immer funktioniert.
Stell es dir so vor
Lineare Suche ist wie die Suche nach deinem Schlüssel in einer Reihe von Manteltaschen. Du prüfst die erste Tasche, dann die nächste, eine nach der anderen, und hörst auf, sobald du ihn findest. Bist du bei der letzten Tasche angekommen, ist der Schlüssel nicht da.
for index, value in enumerate(values):🧥 Jede Tasche der Reihe nach prüfenif value == target:🔑 Ist der Schlüssel hier?return index✅ Gefunden: Suche beendenreturn -1❌ Alle Taschen geprüft: nicht gefundenDie lineare Suche prüft die Elemente einer Sammlung nacheinander, bis sie das Ziel findet. Sie braucht bis zu O(n) Schritte, aber keine Sortierung.
Die lineare Suche prüft die Elemente vom Anfang an, bis der Zielwert gefunden oder das Ende erreicht ist. Die Daten müssen vorher nicht sortiert werden.
So arbeitet der Algorithmus
- Bei Index 0 beginnen.
- Das aktuelle Element mit dem Zielwert vergleichen.
- Bei Übereinstimmung den Index zurückgeben, sonst fortfahren.
- Nach dem letzten Element -1 zurückgeben, wenn kein Treffer vorliegt.
Wann verwendet man das?
- Unsortierte oder kleine Sammlungen.
- Einmalige Suchen, bei denen vorheriges Sortieren mehr kosten würde.
- Das erste Element finden, das eine Bedingung erfüllt, nicht nur einen exakten Wert.
Wann du es nicht brauchst
- Viele Suchen in denselben großen Daten: einmal sortieren und binär suchen, oder ein Set bzw. Dictionary bauen.
- Nur prüfen, ob ein Wert vorhanden ist:
target in valuesmacht dasselbe mit weniger Code.
Lineare Suche (linear search) in Python visualisieren
O(n)Mit Start oder Schritt kannst du jeden Vergleich und jede Datenbewegung verfolgen.
Beispielcode
def linear_search(values, target):
for index, value in enumerate(values):
if value == target:
return index
return -1
print(linear_search([14, 3, 27, 8, 19], 8))
Ergebnis der Ausführung
3
Erklärung des Codes
Die Funktion enumerate() liefert Position und Wert jedes Elements. Sobald der gesuchte Wert auftaucht, gibt die Funktion diese Position zurück, hier 3. Wird die ganze Liste ohne Treffer durchlaufen, gibt sie -1 zurück. Im schlechtesten Fall prüft der Algorithmus alle Elemente, die Komplexität ist also O(n).
Ä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
-1 innerhalb der Schleife zurückgeben
Die Suche gibt nach dem ersten nicht passenden Element auf.
for index, value in enumerate(values):
if value == target:
return index
return -1
for index, value in enumerate(values):
if value == target:
return index
return -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.
- First Negative Index Find where the first negative number appears. Einfach
- Array Minimum Finde den kleinsten Wert in einer Liste. Einfach