Lineare Suche in Python
Die lineare Suche prüft jedes Element von links nach rechts und benötigt keine sortierten Daten.
Was ist die lineare Suche?
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.
Komplexität: Durchschnittlich und im ungünstigsten Fall O(n) Zeit, dazu O(1) zusätzlicher Speicher.
Lineare Suche in Python visualisieren
O(n)Mit Start oder Schritt kannst du jeden Vergleich und jede Datenbewegung verfolgen.
Beispielcode
main.py
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))Erwartete Ausgabe
3So funktioniert es
Beim ersten Treffer wird der Index zurückgegeben. Im ungünstigsten Fall werden alle n Elemente geprüft; die Laufzeit ist O(n).
Ä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.