Lineare Suche

Nach einem Stadtlauf stehen die Startnummern in der Reihenfolge des Zieleinlaufs in der Reihung startnr. Auf welchem Platz ist die Nummer 15 ins Ziel gekommen?

• Suchproblem:gegeben eine Reihung a und ein Suchwert x — gesucht ist der Index, an dem x steht.
• Prinzip:die Elemente der Reihe nach ab Index 0 mit x vergleichen (auch sequenzielle Suche).
• Treffer:sofort abbrechen und den Index zurückgeben — hier 3.
• Kein Treffer:nach dem letzten Element −1 zurückgeben; −1 ist nie ein gültiger Index.
• Doppelte Werte:geliefert wird das erste Vorkommen: die Suche nach 8 ergibt 1, nicht 4.
• Voraussetzung:keine — die Reihung darf unsortiert sein.

static int lineareSuche(int[] a, int x) {
    for (int i = 0; i < a.length; i++) {
        if (a[i] == x) {
            return i;          // erster Treffer: Methode endet sofort
        }
    }
    return -1;                 // alle Elemente geprüft, x nicht dabei
}

Den Aufwand misst man an der Zahl der Vergleiche a[i] == x. Für eine Reihung der Länge \(n\) gilt:

• Bester Fall:x steht an Index 0 — 1 Vergleich.
• Ungünstigster Fall:x steht ganz hinten oder fehlt — \(n\) Vergleiche.
• Treffer an Index i:genau i + 1 Vergleiche.
• Beispiel:in startnr braucht die Suche nach 15 vier, nach 8 zwei und nach 50 sechs Vergleiche (Ergebnis −1).

Tippe zuerst: Klicke den Index an, den die Suche liefern wird (oder das Feld −1), und stelle die Zahl der Vergleiche ein. Starte dann die Suche und vergleiche. Spiele alle Runden durch — auch die mit doppelten und fehlenden Werten.

Halte fest: Die lineare Suche liefert den Index des ersten Treffers nach Index + 1 Vergleichen; fehlt der Wert, prüft sie alle \(n\) Elemente und liefert −1.