Binäre Suche rekursiv

In Kapitel 2 hat eine Schleife die Grenzen links und rechts verschoben. Rekursiv werden die Grenzen als Parameter übergeben: Jeder Aufruf sucht in einem halb so großen Bereich — derselbe Algorithmus, als Selbstaufruf formuliert.

• Teilproblem:„Suche x in a[links] … a[rechts]“ — die Grenzen sind Hilfsparameter wie in 3.2.1.
• Abbruch 1:links > rechts: der Bereich ist leer, Rückgabe −1.
• Abbruch 2:a[mitte] == x: Treffer, Rückgabe mitte.
• Rekursionsschritt:nur in einer Hälfte weitersuchen — rechts von mitte, wenn a[mitte] < x, sonst links davon.
• Startmethode:binSuche(a, x) ruft binSuche(a, x, 0, a.length - 1) auf.
• Endrekursion:jeder Selbstaufruf steht in einem return — deshalb entspricht die Methode genau der Schleife aus Kapitel 2.

static int binSuche(int[] a, int x) {
    return binSuche(a, x, 0, a.length - 1);          // Startaufruf
}

static int binSuche(int[] a, int x, int links, int rechts) {
    if (links > rechts) {
        return -1;                                    // Bereich leer
    }
    int mitte = (links + rechts) / 2;
    if (a[mitte] == x) {
        return mitte;                                 // Treffer
    }
    if (a[mitte] < x) {
        return binSuche(a, x, mitte + 1, rechts);     // rechte Hälfte
    }
    return binSuche(a, x, links, mitte - 1);          // linke Hälfte
}

Aufruf binSuche(a, 48) mit

Der dritte Aufruf liefert 6; die beiden wartenden Aufrufe reichen den Wert unverändert zurück.

Ziehe den Suchwert \(x\) auf dem Zahlenstrahl (oder wähle ihn mit ←/→). Darüber siehst du für jeden Aufruf den Suchbereich als Balken, die Mitte als Punkt. Vergleiche die Zahl der Aufrufe bei 7, 15 und 31 Elementen; ▶ fährt alle Werte ab.

Halte fest: Jeder Aufruf halbiert den Bereich. Verdoppelt sich die Zahl der Elemente von 7 auf 15 und auf 31, kommt jeweils nur ein Aufruf mit Vergleich hinzu.

• Tiefe = Aufrufe:die Methode ruft sich höchstens einmal selbst auf (lineare Rekursion): Die Zahl der Aufrufe ist zugleich die Höhe des Aufrufstapels.
• Speicher:bei einer Million Elementen genügen gut 20 Rahmen — anders als bei der rekursiven linearen Suche aus 3.1.3 mit einem Rahmen je Element.
• Teile und herrsche:halbieren und nur eine Hälfte weiterbearbeiten; in 3.3 werden beide Hälften bearbeitet und die Ergebnisse zusammengeführt.