MINT lernen

Abituraufgaben: Binäre Suche rekursiv

Zwei Aufgaben im Abiturformat — von der Mitgliederliste bis zur Wurzel durch Halbieren.

Dein Fortschritt:
0 / 0 Aufgaben
1

Die Mitgliederliste

AFB I–II

Ein Sportverein speichert die Nachnamen seiner Mitglieder alphabetisch sortiert in einer Reihung namen. Die Suche verwendet compareTo: s.compareTo(t) ist negativ, wenn s alphabetisch vor t steht, 0 bei Gleichheit und sonst positiv.

Material 1: Ausschnitt der Reihung (Länge 10)
Material 2: Methode suche
static int suche(String[] namen, String gesucht, int links, int rechts) {
    if (links > rechts) {
        return -1;
    }
    int mitte = (links + rechts) / 2;
    int v = namen[mitte].compareTo(gesucht);
    if (v == 0) {
        return mitte;
    }
    if (v < 0) {
        return suche(namen, gesucht, mitte + 1, rechts);
    }
    return suche(namen, gesucht, links, mitte - 1);
}
  1. Beschreiben Sie die Rolle von v in der Methode und nennen Sie die Voraussetzung, unter der die Suche korrekt arbeitet. 3 BE
  2. Stellen Sie die Aufrufe von suche(namen, "Hoppe", 0, 9) und suche(namen, "Brandt", 0, 9) jeweils mit links, rechts, mitte und namen[mitte] dar. 5 BE
  3. Ändern Sie die Methode so ab, dass sie bei erfolgloser Suche nicht −1, sondern \(-(p + 1)\) liefert, wobei \(p\) die Position ist, an der der Name einsortiert werden müsste. 4 BE
  4. Schätzen Sie für einen Landesverband mit 80 000 Mitgliedern ab, wie viele Vergleiche eine Suche höchstens braucht und wie viele Rahmen dabei höchstens auf dem Aufrufstapel liegen. 3 BE

Insgesamt 15 BE

Hinweise

Hinweis zu Aufgabe a)
Vergleichen Sie mit der Suche auf Zahlen: Was entspricht dort a[mitte] < x?
Hinweis zu Aufgabe b)
Für „Brandt“: B-r kommt nach B-e, aber vor C.
Hinweis zu Aufgabe c)
Wo stehen links und rechts, wenn der Bereich leer wird?
Hinweis zu Aufgabe d)
Nutzen Sie \(\lfloor \log_2 n \rfloor + 1\) und berücksichtigen Sie den Aufruf mit leerem Bereich.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

v speichert das Ergebnis des alphabetischen Vergleichs des mittleren Namens mit dem gesuchten: 0 bedeutet Treffer, ein negativer Wert, dass der mittlere Name vor dem gesuchten steht (also rechts weitersuchen), ein positiver, dass links weitergesucht wird. Voraussetzung: Die Reihung ist alphabetisch aufsteigend sortiert, und die Sortierung nutzt dieselbe Ordnung wie compareTo.

Erwartungshorizont zu Aufgabe b)

„Hoppe“:

linksrechtsmittenamen[mitte]Entscheidung
094Engelvor Hoppe → rechts
597HoppeTreffer → 7

„Brandt“:

linksrechtsmittenamen[mitte]Entscheidung
094Engelnach Brandt → links
031Beckervor Brandt → rechts
232Celiknach Brandt → links
21——leer → −1
Erwartungshorizont zu Aufgabe c)
static int suche(String[] namen, String gesucht, int links, int rechts) {
    if (links > rechts) {
        return -(links + 1);             // Einfügeposition codiert
    }
    int mitte = (links + rechts) / 2;
    int v = namen[mitte].compareTo(gesucht);
    if (v == 0) {
        return mitte;
    }
    if (v < 0) {
        return suche(namen, gesucht, mitte + 1, rechts);
    }
    return suche(namen, gesucht, links, mitte - 1);
}

Wird der Bereich leer, zeigt links genau auf die Einfügeposition. Für „Brandt“ ist \(p = 2\), Rückgabe −3. Das \(+1\) sorgt dafür, dass auch Position 0 eine negative Zahl ergibt und von einem Treffer unterscheidbar bleibt.

Erwartungshorizont zu Aufgabe d)

\(2^{16} = 65\,536 \le 80\,000 < 2^{17}\), also höchstens \(16 + 1 = 17\) Vergleiche. Da die Methode sich höchstens einmal je Aufruf selbst aufruft, ist die Stapelhöhe gleich der Zahl der Aufrufe: höchstens 17 mit Vergleich plus ein Aufruf mit leerem Bereich, also 18 Rahmen. Das ist unproblematisch.

2

Wurzeln durch Intervallhalbierung

AFB II–III

Die ganzzahlige Wurzel von \(n \ge 0\) ist die größte ganze Zahl \(w\) mit \(w^2 \le n\), z. B. 6 für \(n = 40\). Die abgebildete Methode sucht sie wie eine binäre Suche im Bereich 0 bis \(n\); gestartet wird mit wurzel(n, 0, n).

Material: Methode wurzel
static int wurzel(int n, int links, int rechts) {
    if (links == rechts) {
        return links;
    }
    int mitte = (links + rechts + 1) / 2;
    if ((long) mitte * mitte <= n) {
        return wurzel(n, mitte, rechts);
    }
    return wurzel(n, links, mitte - 1);
}
  1. Analysieren Sie den Aufruf wurzel(40, 0, 40) mit einer Tabelle der Aufrufe. 4 BE
  2. Erläutern Sie, warum die Mitte hier mit (links + rechts + 1) / 2 berechnet wird. Betrachten Sie dazu den Aufruf wurzel(40, 5, 6) mit der üblichen Formel (links + rechts) / 2. 4 BE
  3. Begründen Sie, dass die Methode für jedes \(n \ge 0\) terminiert. 3 BE
  4. Beurteilen Sie die Methode im Vergleich zu einem Verfahren, das \(k = 0, 1, 2, \dots\) durchprobiert, bis \(k^2 > n\) gilt, für \(n = 10^9\). 4 BE

Insgesamt 15 BE

Hinweise

Hinweis zu Aufgabe a)
In jedem Aufruf: mitte berechnen, mitte² mit 40 vergleichen, neue Grenzen notieren.
Hinweis zu Aufgabe b)
Setzen Sie in beide Formeln links = 5 und rechts = 6 ein und verfolgen Sie den nächsten Aufruf.
Hinweis zu Aufgabe c)
Zeigen Sie, dass der Bereich rechts − links in jedem Aufruf echt kleiner wird und nie negativ.
Hinweis zu Aufgabe d)
Zählen Sie die Schritte beider Verfahren. Denken Sie auch an den Datentyp beim Produkt.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)
Aufruflinksrechtsmittemitte²Entscheidung
104020400> 40 → (0, 19)
201910100> 40 → (0, 9)
309525≤ 40 → (5, 9)
459749> 40 → (5, 6)
556636≤ 40 → (6, 6)
666——links = rechts → 6

Rückgabe 6 nach 6 Aufrufen.

Erwartungshorizont zu Aufgabe b)

Gilt mitte * mitte <= n, kann mitte selbst die Lösung sein und bleibt als linke Grenze erhalten. Mit (5 + 6) / 2 = 5 ergäbe sich wegen \(25 \le 40\) der Aufruf wurzel(40, 5, 6) — derselbe Bereich, eine Endlosrekursion mit StackOverflowError. Mit (5 + 6 + 1) / 2 = 6 liegt die Mitte bei zwei Elementen auf dem rechten, sodass im Fall „≤“ der Bereich auf (6, 6) schrumpft.

Erwartungshorizont zu Aufgabe c)

Solange links < rechts ist, gilt \(\text{links} < \text{mitte} \le \text{rechts}\). Im Fall „≤“ steigt links auf mitte (echt größer), im anderen Fall sinkt rechts auf mitte − 1 \(\ge\) links. Der Abstand rechts − links ist eine natürliche Zahl und wird in jedem Aufruf echt kleiner; nach endlich vielen Schritten ist er 0 und die Abbruchbedingung erfüllt.

Erwartungshorizont zu Aufgabe d)

Das Durchprobieren braucht etwa \(\sqrt{n} \approx 31\,623\) Schritte, die Intervallhalbierung nur etwa \(\log_2 10^9 \approx 30\) Aufrufe — rund tausendmal weniger. Die Rekursionstiefe von etwa 30 ist unkritisch. Zu beachten ist, dass mitte * mitte für große \(n\) den Bereich von int übersteigt (\(500\,000\,000^2\)); deshalb rechnet die Methode mit (long). Die Intervallhalbierung ist klar vorzuziehen.