Lineare und binäre Suche

Gesucht ist der Index eines Werts x in einer Reihung a der Länge \(n\) — oder −1, wenn x fehlt. Die Fundnummern einer Stadtbibliothek sind aufsteigend sortiert gespeichert:

• Lineare Suche:ab Index 0 jedes Element mit x vergleichen, beim ersten Treffer abbrechen — funktioniert auf jeder Reihung.
• Binäre Suche:nur auf sortierten Reihungen: das mittlere Element des Suchbereichs links … rechts vergleichen und eine Hälfte ausschließen.
• Mitte:mitte ← (links + rechts) / 2 mit ganzzahliger Division.
• Zu klein / zu groß:a[mitte] < x: links ← mitte + 1 · a[mitte] > x: rechts ← mitte − 1.
• Invariante:kommt x vor, dann liegt es immer im Bereich links … rechts; wird er leer (links > rechts), fehlt x.
• Beispiel:Suche nach 47: binär über die Mitten 36 (Index 7) und 58 (Index 11) zum Treffer an Index 9 — 3 Vergleiche, linear 10.

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

static int binaereSuche(int[] a, int x) {  // a aufsteigend sortiert
    int links = 0, rechts = a.length - 1;
    while (links <= rechts) {
        int mitte = (links + rechts) / 2;
        if (a[mitte] == x) {
            return mitte;
        } else if (a[mitte] < x) {
            links = mitte + 1;
        } else {
            rechts = mitte - 1;
        }
    }
    return -1;                              // Bereich leer
}

Jeder Vergleich ohne Treffer zerlegt den Suchbereich in zwei Teile. Im ungünstigsten Fall liegt x immer im größeren Teil — oder fehlt ganz.

• Bester Fall:beide Verfahren: 1 Vergleich.
• Ungünstigster Fall:linear \(n\), binär \(\lfloor\log_2 n\rfloor + 1\) Vergleiche.
• Durchschnitt:linear \(\frac{n+1}{2}\), wenn x vorkommt; binär knapp unter dem ungünstigsten Fall.

Du bestimmst, wo verglichen wird: Klicke ein Element im Suchbereich an (oder wähle es mit den Pfeiltasten und Enter). Die Reihung wird dort zerlegt, der kleinere Teil nach unten umgelegt. Schaffst du es mit weniger Vergleichen als die Strategien, die ▶ vorführt?

Halte fest: „Immer ganz links“ ist die lineare Suche und braucht \(n\) Vergleiche. Nur der Schnitt in der Mitte garantiert, dass höchstens die Hälfte übrig bleibt — das ist die binäre Suche.