Algorithmen
Lineare Suche
Der simpelste Suchalgorithmus: jedes Element prüfen bis Treffer oder Ende. Funktioniert auf jedem Array, sortiert oder nicht. O(n) im Worst Case.
3LerneinheitenVoraussetzungen:Big-O Notation
Sprache wählen
Sprache
Lerneinheit 1 von 3java + python
Lineare Suche
Der simpelste Suchalgorithmus. So einfach, dass man ihn in jeder Programmiersprache in 3 Zeilen hinschreibt.
Die Idee
Geh durchs Array, prüf jedes Element ob es das gesuchte ist. Stopp bei Treffer, oder am Ende wenn nichts gefunden.
Das ist genau das, was du auch machst, wenn du eine Telefonnummer in einer unsortierten Liste suchst: von oben nach unten durchgehen.
Implementierung
java// snippet
public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) return i;
}
return -1;
}Komplexität
| Fall | Vergleiche |
|---|---|
| Best Case (Element ist erstes) | 1 |
| Average Case (zufällig im Array) | |
| Worst Case (Element ist letztes oder fehlt) |
→ O(n) im Worst und Average Case.
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 (n < 100): Overhead anderer Verfahren lohnt sich nicht
- Bei unsortierten Daten: einzige Option ohne vorher zu sortieren
- Bei einmaligen Suchen: lohnt sich kein Sortier-Aufwand
- Wenn das erste Vorkommen gesucht wird, nicht ein beliebiges
In der Praxis: Array.indexOf(), List.contains(), Python's in-Operator nutzen alle intern lineare Suche.