Lineare Suche
Die lineare Suche ist das, was Sie tun, wenn Sie einen Namen auf einer unsortierten Liste suchen: oben anfangen und nach unten lesen, bis Sie ihn finden. Es ist die einfachste Suche überhaupt, sie funktioniert mit jeder Liste, und für kurze Listen reicht sie oft völlig aus.
Die Idee
Vergleichen Sie den Zielwert mit dem ersten Wert der Liste. Sind sie gleich, hören Sie auf: Der Zielwert steht an Platz 1. Sonst vergleichen Sie ihn mit dem zweiten Wert, dann mit dem dritten und so fort. Passt auch der letzte Wert nicht, ist der Zielwert nicht in der Liste. Über die Liste muss vorher nichts bekannt sein: Sie muss nicht sortiert sein, und die Werte können alles sein, was sich auf Gleichheit prüfen lässt.
Ein Beispiel
Suchen Sie in 5, 1, 4, 2, 8 nach 4. Ist 5 gleich 4? Nein. 1? Nein. 4? Ja: gefunden an Platz 3 nach 3 Vergleichen. Suchen Sie nun in derselben Liste nach 7. Jeder der fünf Werte wird geprüft, keiner passt, also lautet die Antwort nach 5 Vergleichen: 7 kommt nicht vor.
Wie viele Vergleiche
Ein Wert an Platz k braucht k Vergleiche. Ist der Zielwert an jedem Platz gleich wahrscheinlich, sind das im Durchschnitt (n + 1)/2 Vergleiche: 20,5 bei 40 Werten. Ein fehlender Wert braucht immer n, denn erst nach dem letzten Vergleich steht fest, dass kein Wert gepasst hat. Der Aufwand wächst also proportional zur Länge der Liste, geschrieben O(n).
Schnellere Suchen brauchen Ordnung
Die lineare Suche kann nichts überspringen, denn in einer unsortierten Liste kann jeder Wert überall stehen. Ist eine Liste sortiert, sagt ein Vergleich mehr als gleich oder nicht: Er zeigt, auf welcher Seite der Zielwert liegt. Die binäre Suche nutzt das, um die Liste bei jedem Schritt zu halbieren, und braucht etwa log₂ n Vergleiche, höchstens 6 bei 40 Werten. Sortieren kostet aber auch Zeit, daher ist für eine Liste, die nur einmal durchsucht wird, die lineare Suche oft die bessere Wahl.
Kleine Verbesserungen
Eine Version mit Wächter (Sentinel) setzt den Zielwert vor der Suche ans Ende der Liste, sodass die Schleife nur auf einen Treffer prüfen muss und nicht auch auf das Listenende. Rückt ein Wert bei jedem Fund einen Platz nach vorn oder ganz an den Anfang, werden oft gesuchte Werte mit der Zeit billiger. Am schlimmsten Fall von n Vergleichen ändert beides nichts.
Selbst ausprobieren
Öffnen Sie die App, wählen Sie unter „Suchen nach“ einen Wert und drücken Sie „Schritt“. Die gestrichelte Linie zeigt die Höhe des Zielwerts, jeder Wert wird beim Prüfen hervorgehoben und verblasst, sobald er ausgeschlossen ist, und ein Treffer wird grün. Suchen Sie einen Wert, der nicht in der Liste steht, um einen vollen Durchlauf zu sehen, oder schalten Sie „Beim ersten Treffer stoppen“ aus und wählen Sie „Wenige verschiedene“, um mehrere Treffer zu finden.
Häufig gestellte Fragen
Welche Zeitkomplexität hat die lineare Suche?
O(n) im schlimmsten und im durchschnittlichen Fall und O(1) im besten Fall, wenn der Zielwert der erste Wert ist. Zusätzlicher Speicher ist nicht nötig.
Was ist der Unterschied zwischen linearer und binärer Suche?
Die lineare Suche prüft jeden Wert der Reihe nach und funktioniert mit jeder Liste. Die binäre Suche funktioniert nur mit einer sortierten Liste, halbiert aber bei jedem Schritt den Teil, in dem der Zielwert stehen kann, und braucht daher etwa log₂ n statt bis zu n Vergleiche.
Braucht die lineare Suche eine sortierte Liste?
Nein. Das ist ihr größter Vorteil. In einer sortierten Liste kann sie aufhören, sobald sie den Platz passiert, an dem der Zielwert stehen müsste, bleibt aber langsamer als die binäre Suche.
Wo wird die lineare Suche verwendet?
Überall, wo Listen kurz oder unsortiert sind: um ein Element in einem kleinen Array zu finden, eine Datei oder einen Datenstrom zu durchlaufen, der sich nur der Reihe nach lesen lässt, oder jedes Element auf eine Bedingung zu prüfen. Viele Bibliotheksfunktionen, etwa indexOf in JavaScript und list.index in Python, sind lineare Suchen.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Lineare Suche ausprobieren