Komplexität
| Fall | Vergleiche |
|---|
| Best Case (Element ist erstes) | 1 |
| Average Case (Element gleichverteilt im Array, garantiert vorhanden) | (n+1)/2 ≈ n/2 |
| Worst Case (Element ist letztes oder fehlt) | n |
→ O(n) im Worst und Average Case. Die Average-Formel (n+1)/2 gilt unter der Annahme, dass das Element garantiert im Array vorhanden ist und jede Position gleich wahrscheinlich ist. Bei erfolgreicher Suche mit gleichverteiltem Treffer im Schnitt etwa n/2 Vergleiche. Bei erfolgloser Suche werden alle n Elemente geprüft, also genau n Vergleiche. Bei Trefferwahrscheinlichkeit p < 1 liegt der Erwartungswert irgendwo dazwischen, formal p · (n+1)/2 + (1-p) · n.
Klausur-Trace: lineare Suche Schritt für Schritt
Zwei typische Aufgabenstellungen aus echten Algorithmen-Klausuren:
Beispiel A: Treffer in der Mitte
Array [7, 2, 9, 4, 11] (Indizes 0..4), gesucht Target 9.
| Iter | i | arr[i] | arr[i] == 9? | Vergleiche bisher |
|---|
| 1 | 0 | 7 | nein | 1 |
| 2 | 1 | 2 | nein | 2 |
| 3 | 2 | 9 | ja → return 2 | 3 |
Drei Vergleiche, Index 2 zurück. Bei Target an Position k braucht lineare Suche genau k+1 Vergleiche.
Beispiel B: erfolglose Suche (Worst Case)
Gleiches Array, gesucht Target 5.
| Iter | i | arr[i] | arr[i] == 5? | Vergleiche bisher |
|---|
| 1 | 0 | 7 | nein | 1 |
| 2 | 1 | 2 | nein | 2 |
| 3 | 2 | 9 | nein | 3 |
| 4 | 3 | 4 | nein | 4 |
| 5 | 4 | 11 | nein | 5 |
Nach Schleifen-Ende: return -1. Fünf Vergleiche, das ist der Worst Case bei n=5. Bei jeder erfolglosen Suche werden alle Elemente angefasst, der Aufwand ist exakt n Vergleiche, anders als bei der binären Suche gibt es keine Abbruchbedingung vor dem Array-Ende, weil ein unsortiertes Array keine Garantien über die Position des Targets liefert. Selbst wenn das Target an der vorletzten Position stehen würde, müsste man die letzte trotzdem prüfen.
Beispiel C: Klausur-Klassiker, erster Treffer bei Duplikaten
Array [4, 2, 4, 7, 4], gesucht Target 4. Standard-Variante liefert Index 0, nicht 2 oder 4. Die Schleife bricht beim ersten Match ab. Wenn die Klausur den letzten Treffer will, brauchst du eine angepasste Schleife (rückwärts iterieren oder Index in einer Variablen merken statt sofort zu returnen).
Eigenschaften
- ✅ Funktioniert auf JEDER Liste, sortiert oder unsortiert
- ✅ Einfach zu implementieren: 3 Zeilen Code
- ✅ Kein Vorbereitungs-Aufwand: kein Sortieren nötig
- ❌ Lineare Skalierung: bei einer Million Einträgen bis zu eine Million Vergleiche
Wann sinnvoll?
- Bei kleinen Arrays: Overhead anderer Verfahren lohnt sich nicht. Die genaue Schwelle ist hardware-abhängig, in der Praxis liegt sie oft bei
n < 10–30 (Cache-Lokalität und kleine Konstanten von linearer Suche schlagen den Overhead von binärer Suche).
- Bei unsortierten Daten ohne Zusatzindex: Standard-Option ohne vorher zu sortieren. Mit Hash-Tabelle/Map auf den Daten geht's auch schneller.
- Bei einmaligen Suchen: lohnt sich kein Sortier-Aufwand
- Wenn das erste Vorkommen gesucht wird, nicht ein beliebiges
In der Praxis nutzen verschiedene Standard-Bibliotheken lineare Suche für Listen ohne Index, weil dort Random-Access nicht O(1) ist. Beispiele:
- Java:
List.contains(), List.indexOf() auf einer ArrayList/LinkedList sind linear. Für primitive Arrays: eigene Schleife oder Stream/Arrays.asList.
- JavaScript:
Array.prototype.indexOf() und Array.prototype.includes() sind linear.
- Python:
x in list und list.index(x) sind linear. Achtung: x in set und x in dict sind hash-basiert und durchschnittlich O(1), also nicht linear.
