Lineare Suche
Prüft jedes Element der Reihe nach, bis der gesuchte Wert auftaucht.
- Vergleiche 0
- Ergebnis noch offen
- Vergleich
- Treffer
- ausgeschlossen
Pseudocode
1 for i from 0 to n - 1
2 if a[i] == target
3 return i
4 return -1
Schritt-Log
Funktionsweise, Laufzeit und Speicher
Die lineare Suche ist der einfachste Suchalgorithmus überhaupt. Sie läuft das Array Element für Element von vorne nach hinten ab und vergleicht jeden Wert mit dem Suchschlüssel. Sobald die Werte übereinstimmen, gibt sie den Index zurück. Wird das Array komplett durchlaufen ohne Treffer, liefert sie -1. Weil im schlimmsten Fall jedes Element angefasst werden muss, ist die Laufzeit linear (O(n)) im Average und Worst Case; im Best Case sitzt der Treffer auf Index 0, was eine konstante Zeit ergibt (O(1)). Es wird kein zusätzlicher Speicher gebraucht (O(1)). Der große Vorteil: die lineare Suche stellt keine Anforderungen an das Array, es muss insbesondere nicht sortiert sein, und sie funktioniert auch auf Streams oder verketteten Listen, die nur sequentiellen Zugriff bieten.
Komplexität
- Best Case
O(1) - Average Case
O(n) - Worst Case
O(n) - Zusatz-Speicher
O(1)
Wann verwenden?
Funktioniert auf unsortierten Daten und ist die einzige Wahl, wenn die Daten in einer einfachen Liste oder einem Stream liegen, der nur sequentiellen Zugriff erlaubt. Bei größeren, sortierten Datenmengen mit Random-Access ist die binäre Suche um Größenordnungen schneller.