Stell dir vor, du suchst in einem Stapel ungeordneter Karten nach einer bestimmten Zahl. Was machst du? Du nimmst die erste Karte, schaust sie an, legst sie weg, nimmst die nächste... und so weiter, bis du die gesuchte Karte findest oder alle Karten durchgeschaut hast. Genau so funktioniert die lineare Suche.
Grundidee
Die lineare Suche geht die Liste von Anfang bis Ende durch und vergleicht jedes Element mit dem gesuchten Wert. Sobald eine Übereinstimmung gefunden wird, gibt sie den Index zurück. Wenn das Ende der Liste erreicht wird, ohne eine Übereinstimmung zu finden, gibt sie an, dass das Element nicht vorhanden ist.
Python-Implementierung
def lineare_suche(liste, zielwert):
for i in range(len(liste)):
if liste[i] == zielwert:
return i # Index des gefundenen Elements zurückgeben
return -1 # -1 bedeutet: nicht gefunden
fruechte = ["Apfel", "Banane", "Kirsche", "Mango", "Orange"]
ergebnis = lineare_suche(fruechte, "Kirsche")
print(ergebnis) # 2
ergebnis2 = lineare_suche(fruechte, "Traube")
print(ergebnis2) # -1 (nicht gefunden)
Die Rückgabe von -1 bei einem nicht gefundenen Element ist eine verbreitete Konvention. Da gültige Indizes immer größer oder gleich 0 sind, weiß der Aufrufer sofort: Wert -1 bedeutet "nicht gefunden".
Visualisierung
Suche nach 7 in [3, 9, 7, 1, 5]:
| Schritt | Index | Element | Übereinstimmung? |
|---|---|---|---|
| 1 | 0 | 3 | Nein |
| 2 | 1 | 9 | Nein |
| 3 | 2 | 7 | Ja! → gib Index 2 zurück |
Effizienz
Im besten Fall (Element an erster Stelle) braucht die lineare Suche nur 1 Vergleich.
Im schlechtesten Fall (Element nicht vorhanden oder an letzter Stelle) braucht sie n Vergleiche — für jede Liste mit n Elementen.
Im Durchschnitt werden n/2 Vergleiche benötigt.
Das nennt man O(n) — lineare Zeitkomplexität.
Wenn du eine Suche in einer unsortierten Liste durchführst, ist die lineare Suche oft die einzige Möglichkeit. Bei einer sortierten Liste gibt es mit der binären Suche eine deutlich schnellere Alternative.
Wann die lineare Suche verwenden?
Die lineare Suche ist sinnvoll, wenn:
- Die Liste klein ist
- Die Liste nicht sortiert ist und du nicht sortieren möchtest
- Du nur einmal suchst (Sortieren wäre aufwändiger als einmaliges Durchsuchen)
- Du nach dem ersten Vorkommen eines Elements suchst
Alle Vorkommen finden
Eine Variante, die alle Positionen des gesuchten Elements findet:
def alle_positionen(liste, zielwert):
positionen = []
for i in range(len(liste)):
if liste[i] == zielwert:
positionen.append(i)
return positionen
noten = [2, 1, 3, 1, 2, 1, 4]
print(alle_positionen(noten, 1)) # [1, 3, 5]
Pythons eingebaute Methode liste.index(wert) macht im Grunde dasselbe wie eine lineare Suche — sie gibt den Index des ersten Vorkommens zurück und wirft einen ValueError, wenn der Wert nicht vorhanden ist. Mit wert in liste kannst du prüfen, ob ein Element vorhanden ist (ebenfalls lineare Suche intern).
Übungsaufgaben
Wie viele Vergleiche benötigt eine lineare Suche im schlechtesten Fall für eine Liste mit 20 Elementen?
Antwort anzeigen
Du hast eine Liste mit 1000 Elementen. Warum könnte es besser sein, die Liste zuerst zu sortieren und dann eine binäre Suche durchzuführen, anstatt eine lineare Suche zu verwenden — auch wenn das Sortieren Zeit kostet?