Lineare Suche.

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. Du lernst hier die Komplexität (O(n) Worst Case, O(1) Best Case, im Durchschnitt ∼ n/2 Vergleiche bei erfolgreicher Suche und gleichverteiltem Treffer), die typische Klausur-Falle beim return-Verhalten bei Duplikaten (Standard liefert ersten Treffer, z. B. [4, 2, 4] mit Target 4 → Index 0), die Implementierung in Java und Python, wann lineare Suche besser ist als binäre Suche (unsortierter Input, sehr kleines n, einmalige Suche ohne Sortier-Vorlauf) und die Stop-Bedingung (Worst Case voller Durchlauf wenn nicht gefunden, Best Case Treffer am Anfang).

Was du in der Klausur können musst:

• Idee: vom ersten Element bis zum letzten durchlaufen, jedes mit dem Suchwert vergleichen
• Komplexität: O(n) Worst-Case und Average-Case, O(1) Best-Case (Treffer am Anfang)
• Voraussetzung: keine, funktioniert auf unsortierten Daten
• Anwendung: Standard wenn Daten unsortiert sind oder die Liste klein ist

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.

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.

Inline-Trace für [3, 8, 1, 7, 5]

Target 7 (Treffer an Index 3):

Target 99 (nicht im Array, erfolglose Suche):

Nach Schleife: return -1. Bei erfolgreicher Suche stoppt die Schleife sofort beim Treffer, bei erfolgloser Suche müssen alle n Elemente geprüft werden.

Implementierung

public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

def linear_search(arr, target):
    for i, value in enumerate(arr):
        if value == target:
            return i
    return -1

Komplexität

→ 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.

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.

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.

Lineare Suche live

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:

• Setz das Target auf einen Wert ganz vorne im Array: wenig Vergleiche
• Setz das Target auf einen Wert ganz hinten im Array: viele Vergleiche
• Setz das Target auf einen Wert außerhalb (z.B. 99): n Vergleiche, nicht gefunden

In dieser Visualisierung liegen kleinere Werte links und größere rechts, das ist nur eine Anzeigewahl. Allgemein hängt die Anzahl Vergleiche bei linearer Suche nur von der Position des Treffers ab, nicht vom Wert selbst.

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.

---

Code-Stepper: Lineare Suche Zeile für Zeile

Wir suchen die 7 im Array [3, 8, 1, 7, 5]. Du siehst den Index i wandern und nach jedem Vergleich den Counter vergleiche mitzählen. So wird sichtbar warum der Aufwand vom Index des Treffers abhängt, nicht vom Wert.