Der simpelste Suchalgorithmus: jedes Element prüfen bis Treffer oder Ende. Funktioniert auf jedem Array, sortiert oder nicht. O(n) im Worst Case.
Lineare Suche prüft jedes Element der Reihe nach, bis sie das Gesuchte findet oder das Ende des Arrays erreicht. Funktioniert auf jedem Array, sortiert oder unsortiert. Komplexität: O(n) im Worst-Case.
Was du in der Klausur können musst:
In Klausuren oft gefragt: wann ist Lineare Suche die richtige Wahl?. Antwort: bei unsortierten Daten oder wenn Sortieren teurer wäre als die einmalige Suche. Bei sortierten Daten und mehrfachen Suchen lohnt sich Binäre Suche stattdessen.
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.
public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) return i;
}
return -1;
}| 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.
In der Praxis: Array.indexOf(), List.contains(), Python's in-Operator nutzen alle intern lineare Suche.
Alle Tabs der Lerneinheit (Erklärung · Interaktiv · Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur — und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Lineare Suche prüft jedes Element der Reihe nach, bis sie das Gesuchte findet oder das Ende des Arrays erreicht. Funktioniert auf jedem Array, sortiert oder unsortiert. Komplexität: O(n) im Worst-Case.
Der intuitive Sortieralgorithmus: zwei verschachtelte Schleifen, größere Werte blubbern nach oben. Einfach zu erklären, in der Praxis aber zu langsam: O(n²).
Teile und Herrsche. Garantierte O(n log n) durch rekursives Halbieren plus Merge. Stabil, aber braucht O(n) Zusatzspeicher. Klausur-Klassiker schlechthin.
Der schnellste der Klassiker im Average Case: O(n log n), in-place, partitioniert um einen Pivot. Bei sortiertem Input rutscht er aber auf O(n²) ab.
Was du in der Klausur können musst:
In Klausuren oft gefragt: wann ist Lineare Suche die richtige Wahl?. Antwort: bei unsortierten Daten oder wenn Sortieren teurer wäre als die einmalige Suche. Bei sortierten Daten und mehrfachen Suchen lohnt sich Binäre Suche stattdessen.
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.
public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) return i;
}
return -1;
}Java: Index zurückgeben bei Treffer, sonst -1 für 'nicht gefunden'.
def linear_search(arr, target):
for i, value in enumerate(arr):
if value == target:
return i
return -1Python: enumerate() liefert Index und Wert in einem. Logik identisch zur Java-Variante.
| Fall | Vergleiche |
|---|---|
| Best Case (Element ist erstes) | 1 |
| Average Case (zufällig im Array) | n/2 |
| Worst Case (Element ist letztes oder fehlt) | n |
→ O(n) im Worst und Average Case.
In der Praxis: Array.indexOf(), List.contains(), Python's in-Operator nutzen alle intern lineare Suche.
Schau zu, wie der Algorithmus Element für Element durchgeht. Der orange Highlight wandert von links nach rechts, bis er das Target findet (oder das Array zu Ende ist).
Probier folgendes:
Interaktive Visualisierung
Vergleicht lineare und binäre Suche mit Schritt-Counter pro Algorithmus.
Faustregel zum Mitnehmen: Lineare Suche ist O(n). Der Aufwand wächst genau proportional zur Eingabe-Größe. Bei 100 Elementen maximal 100 Vergleiche, bei einer Million entsprechend.
Klausurfragen mit Lösungen (6)
Antwort: O(n)
Erklärung: Im Worst Case ist das Element ganz hinten oder gar nicht im Array. Dann muss jedes der n Elemente einmal geprüft werden: O(n).
Antwort: Keine Voraussetzung: funktioniert auf jedem Array
Erklärung: Lineare Suche funktioniert auf jedem Array, sortiert oder nicht. Genau das ist ihr großer Vorteil gegenüber binärer Suche, die ein sortiertes Array verlangt.
Antwort: Etwa 1.000.000
Erklärung: Im Worst Case: alle n Elemente werden einmal geprüft. Bei 1 Million Elementen sind das 1 Million Vergleiche. Genau deshalb skaliert lineare Suche schlecht für große Datenmengen.
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) return i;
}
return -1;Antwort: Gibt -1 zurück
Erklärung: Wenn die Schleife durchläuft ohne `return i` zu erreichen, kommt das `return -1` am Ende dran. Das ist die Konvention für 'nicht gefunden'.
Antwort: 25 (Toleranz ±1)
Erklärung: Im Average Case sind im Schnitt n/2 Vergleiche nötig: das Element ist gleichverteilt irgendwo im Array. Bei n=50 → 25 Vergleiche durchschnittlich. Worst Case wäre 50, Best Case 1.
Typ: Zahlen-Eingabe
Antwort: Wahr
Erklärung: Genau das ist ihr Hauptvorteil: keine Sortierung nötig. Sie prüft jedes Element der Reihe nach. Binäre Suche dagegen braucht zwingend ein sortiertes Array.
Typ: Wahr/Falsch