Python-Algorithmen

Lineare Suche (linear search) in Python

In dieser Lektion implementierst du die lineare Suche, um die Position eines Werts in einer Liste zu finden.

  • Fortgeschritten
  • 2 Min. Lesezeit
  • 1 ausführbares Beispiel

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.

Von Manteltaschen zum Code
for index, value in enumerate(values):🧥 Jede Tasche der Reihe nach prüfen
if value == target:🔑 Ist der Schlüssel hier?
return index✅ Gefunden: Suche beenden
return -1❌ Alle Taschen geprüft: nicht gefunden
Ein Element nach dem anderen prüfen; beim ersten Treffer aufhören.
In einem Satz

Die 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

  1. Bei Index 0 beginnen.
  2. Das aktuelle Element mit dem Zielwert vergleichen.
  3. Bei Übereinstimmung den Index zurückgeben, sonst fortfahren.
  4. 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.

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 values macht 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

Code ausführen →
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))
Run-Button für dieses Beispiel erstellen

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.

  1. Teste mit einer leeren Liste, einer Liste mit nur einem Element und einer Liste mit doppelten Werten.
  2. Gib den Zustand nach jedem Schritt aus, um den Algorithmus bei der Arbeit zu beobachten.
  3. Miss die Laufzeit mit 100, 1.000 und 10.000 Elementen und vergleiche sie mit einer anderen Lösung.
Im Python-Compiler ausführen →

Häufige Fehler

-1 innerhalb der Schleife zurückgeben

Die Suche gibt nach dem ersten nicht passenden Element auf.

Problem
for index, value in enumerate(values):
    if value == target:
        return index
    return -1
Lösung
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.

Alle Challenges