Zum Hauptinhalt springen

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​

Mini-QuizWie arbeitet lineare Suche?

Suche sitzt! Als Nächstes: Minimum selbst finden.