Lineare Suche
Idee
Schau jedes Element an, bis du es findest – oder die Liste zu Ende ist.
def lineare_suche(liste, gesucht):
for i, wert in enumerate(liste):
if wert == gesucht:
return i
return -1
daten = [4, 8, 15, 16, 23, 42]
print(lineare_suche(daten, 15)) # 2
print(lineare_suche(daten, 99)) # -1
Warum wichtig?
- einfach zu verstehen
- funktioniert immer
- bei großen Listen kann es viele Schritte brauchen
Rate mal!
Worst case bei 1000 Elementen?
Auflösung
Bis zu 1000 Vergleiche, wenn das Element fehlt oder ganz hinten ist.
Probiere es selbst
Experiment 1
Suche deinen Namen in einer Liste.
Experiment 2
Zähle Vergleiche mit einer Variable.
Experiment 3
Suche in Dict-Liste nach name-Feld.
Übungen
Level 1
Funktion die True/False zurückgibt (gefunden?).
Level 2
Index zurückgeben.
Experiment 3 / Level 3
Anzahl Schritte printen.
Level-1-Lösung
def enthalten(liste, x):
for w in liste:
if w == x:
return True
return False
Mini-Quiz
Suche sitzt! Als Nächstes: Minimum selbst finden.