- Zielwert
- Verglichen
- Ausgeschlossen
- Gefunden
Lineare Suche
Die lineare Suche ist der einfachste Weg, einen Wert zu finden: Beginnen Sie am Anfang und prüfen Sie jeden Wert der Reihe nach, bis er auftaucht. Sie funktioniert mit jeder Liste, ob sortiert oder nicht. Wählen Sie den gesuchten Wert, spielen Sie die Suche ab oder gehen Sie sie Vergleich für Vergleich durch, und sehen Sie, wie der Aufwand davon abhängt, wo der Wert steht und ob er überhaupt vorkommt. Drücken Sie „Abspielen“, um die Suche anzusehen, oder gehen Sie mit „Schritt“ und „Zurück“ einen Vergleich nach dem anderen durch. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Die gestrichelte Linie markiert den Zielwert. Wählen Sie den Wert, die Anzahl der Balken und ihre Startreihenfolge, oder geben Sie eigene Zahlen ein. Schalten Sie „Beim ersten Treffer stoppen“ aus, um alle Treffer zu finden. Ist das Feld ausgewählt, gehen die Pfeiltasten schrittweise vor, die Leertaste startet und pausiert, und Pos1 und Ende springen zum Anfang und zum Ende.
Wie es funktioniert
- Wählen Sie den gesuchten Wert, die Anzahl der Balken und ihre Startreihenfolge. Oder geben Sie eigene Zahlen ein.
- Drücken Sie „Abspielen“ oder gehen Sie mit „Schritt“ und „Zurück“ einen Vergleich nach dem anderen durch. Ziehen Sie den Schrittregler, um an eine beliebige Stelle der Suche zu springen.
- Schalten Sie „Beim ersten Treffer stoppen“ aus, um jeden Wert zu prüfen und alle Treffer zu finden.
So funktioniert die lineare Suche
Vergleichen Sie den ersten Wert mit dem Zielwert. Sind sie gleich, sind Sie fertig. Wenn nicht, geht es mit dem zweiten Wert weiter, dann mit dem dritten und so fort. Erreichen Sie das Ende der Liste ohne Treffer, ist der Zielwert nicht in der Liste. Vorbereitung ist nicht nötig: Die Liste muss nicht sortiert sein.
Wie viele Vergleiche
Ein Wert an Platz k wird nach k Vergleichen gefunden. Im besten Fall ist es ein Vergleich, wenn der Zielwert vorne steht. Im schlimmsten Fall sind es n, wenn er zuletzt steht oder fehlt, denn erst nach der Prüfung aller Werte ist sicher, dass er nicht vorkommt. Im Durchschnitt braucht ein Wert, der in der Liste steht, etwa (n + 1)/2. Bei einer sortierten Liste ist die binäre Suche weit besser: etwa log₂ n Vergleiche, 6 statt bis zu 40 bei 40 Werten.
Häufig gestellte Fragen
Wie funktioniert die lineare Suche?
Sie prüft die Werte einer Liste einen nach dem anderen, vom ersten bis zum letzten, bis sie den Zielwert findet oder keine Werte mehr übrig sind. Sie heißt auch sequenzielle Suche.
Welche Zeitkomplexität hat die lineare Suche?
O(n): Im schlimmsten Fall, wenn der Zielwert zuletzt steht oder fehlt, vergleicht sie ihn mit allen n Werten. Im Durchschnitt braucht ein Zielwert, der in der Liste steht, etwa (n + 1)/2 Vergleiche.
Wann ist die lineare Suche eine gute Wahl?
Bei kurzen Listen, bei unsortierten Listen, die nur ein- oder zweimal durchsucht werden, und bei Daten, die sich nur der Reihe nach lesen lassen, etwa einem Datenstrom. Erst zu sortieren, um die binäre Suche nutzen zu können, lohnt sich nur, wenn Sie oft suchen.
Warum kostet ein fehlender Wert am meisten?
Weil nichts der linearen Suche sagt, früher aufzuhören. Ein Treffer lässt sich nur ausschließen, indem jeder Wert geprüft wird, also braucht ein Wert, der nicht in der Liste steht, immer n Vergleiche.
Werden meine Zahlen irgendwohin gesendet?
Nein. Die Suche läuft in Ihrem Browser, und Ihre letzten Einstellungen bleiben im lokalen Speicher dieses Browsers.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Zum Editor