MINT lernen

Übungen: Binäre Suche rekursiv

Zehn Übungen zur rekursiven binären Suche — von der Tracetabelle bis zur Gipfelsuche.

Dein Fortschritt:
0 / 0 Aufgaben
1

Übungsaufgaben

Zehn Übungen zum Klicken, Zuordnen, Rechnen und Knobeln — von AFB I bis AFB III. Jede Übung gibt dir sofort Rückmeldung; wenn du nicht weiterkommst, helfen die gestuften Tipps.

A1
Was die rekursive binäre Suche ausmacht
AFB I

Nenne alle zutreffenden Aussagen über die Methode binSuche(a, x, links, rechts).

Mehrere Antworten sind richtig. Markiere alle zutreffenden und klicke dann auf „Auswahl prüfen“.
Ein Selbstaufruf je Aufruf, immer in einem return — endrekursiv. Bei 1000 Elementen sind es höchstens 10 Vergleiche. links > rechts meldet einen leeren Bereich: nicht gefunden.
Ansatz: Wie viele Selbstaufrufe werden in einem Aufruf tatsächlich ausgeführt?
Weiter: Was bedeutet ein leerer Suchbereich?
A2
Bausteine der Methode
AFB I

Ordne jede Zeile der rekursiven binären Suche ihrer Rolle zu.

Ziehe jede Karte in den passenden Korb — oder wähle sie mit Enter aus und drücke dann die Ziffer des Korbs (0 legt sie zurück).
1Abbruchbedingung
2Rekursionsschritt
3Startaufruf
4Vorbereitung im Rumpf
Zwei Abbruchfälle (leer, Treffer), zwei mögliche Selbstaufrufe — von denen in jedem Aufruf nur einer ausgeführt wird. Der Startaufruf steht in der Startmethode.
Ansatz: Welche Zeilen enthalten den Methodennamen, welche nicht?
Weiter: Der Startaufruf nutzt 0 und a.length - 1.
A3
Stimmt's? — Suche nach 20
AFB I

Gegeben ist int[] b = {4, 9, 15, 20, 26, 33, 38, 41, 47, 55}; und der Aufruf binSuche(b, 20, 0, 9). Lies aus der Reihung ab, ob die Aussagen stimmen.

5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann startest du die Serie mit „Neue Runde“ neu.
Aussage 1 von 5

Auch wenn 20 weit vorn steht, braucht die binäre Suche hier 4 Aufrufe — die lineare Suche wäre mit 4 Vergleichen gleich schnell. Der Vorteil zeigt sich erst bei großen Reihungen.
Ansatz: Berechne mitte mit ganzzahliger Division.
Weiter: Notiere nach jedem Aufruf die neuen Grenzen.
A4
Tracetabelle einer erfolglosen Suche
AFB II

Gegeben ist int[] c = {3, 12, 18, 27, 31, 39, 44, 52, 60, 68, 75};. Stelle die Aufrufe von binSuche(c, 50, 0, 10) dar.

Fülle alle Felder aus und prüfe dann. Enter in einem Feld prüft ebenfalls. Wahrheitswerte als wahr oder falsch.
Aufruflinksrechtsmittec[mitte]
1010
210
36
47
57—leer → −1
Vier Vergleiche (\(\lfloor \log_2 11 \rfloor + 1 = 4\)) und ein fünfter Aufruf mit leerem Bereich (7 > 6), der −1 liefert.
Ansatz: Nach jedem Vergleich: links ← mitte + 1 oder rechts ← mitte − 1.
Weiter: Der letzte Aufruf hat links > rechts.
A5
Höchstens wie viele Vergleiche?
AFB II

Berechne die größte Zahl von Vergleichen mit a[mitte] für verschiedene Längen \(n\).

Arbeite die Kette Schritt für Schritt ab: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
  1. n = 100: Vergleiche
  2. n = 1000: Vergleiche
  3. n = 1 000 000: Vergleiche
  4. n = 2 000 000: Vergleiche
\(\lfloor \log_2 n \rfloor + 1\): \(2^6 = 64 \le 100 < 128\) ergibt 7, \(2^9 = 512 \le 1000\) ergibt 10, \(2^{19} \le 10^6 < 2^{20}\) ergibt 20. Doppelt so viele Elemente — ein Vergleich mehr.
Ansatz: Suche die größte Zweierpotenz, die höchstens n ist.
Weiter: Ist \(2^k \le n < 2^{k+1}\), sind es \(k + 1\) Vergleiche.
A6
Schleife und Selbstaufruf
AFB II Mix

Die iterative binäre Suche aus Kapitel 2 und die rekursive Fassung entsprechen sich Zeile für Zeile. Vergleiche sie, indem du passende Teile verbindest.

Klicke links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
Die Schleifenbedingung wird verneint zur Abbruchbedingung, das Neubelegen der Grenzen wird zum Selbstaufruf mit neuen Parametern — das ist das Übersetzungsschema für Endrekursion aus 3.1.3.
Ansatz: Wo werden in der rekursiven Fassung die Grenzen verändert?
Weiter: Die Bedingung, unter der weitergesucht wird, wird zur Bedingung, unter der aufgehört wird.
A7
Zwei Fehler in der Suche
AFB II

Überprüfe die Methode und korrigiere die fehlerhaften Zeilen.

Klicke die fehlerhaften Zeilen an — dann klappt ein Feld auf, in das du die richtige Zeile schreibst. Geprüft werden Auswahl und Korrekturen.
Mit >= wird ein Bereich aus einem Element nie geprüft — steht x genau dort, meldet die Methode −1. Mit mitte statt mitte + 1 bleibt bei zwei Elementen der Bereich gleich: StackOverflowError.
Ansatz: Teste mit einer Reihung aus einem einzigen Element.
Weiter: Wird der Bereich in jedem Selbstaufruf echt kleiner?
A8
Das erste Vorkommen
AFB III

In {2, 5, 5, 5, 8, 9} findet binSuche die 5 an Index 2 — gesucht ist aber das erste Vorkommen (Index 1). Verändere die Methode, indem du die Lücken füllst.

Wähle in jedem Menü den passenden Eintrag und prüfe dann alle auf einmal.
static int erstes(int[] a, int x, int links, int rechts) {
    if (links > rechts) return -1;
    int mitte = (links + rechts) / 2;
    if (a[mitte] < x) return erstes(a, x, mitte + 1, rechts);
    if (a[mitte] > x) return erstes(a, x, links, mitte - 1);
    int weiter = erstes(a, x, , );
    if (weiter == -1) return ;
    return ;
}
Nach einem Treffer wird links davon weitergesucht. Findet sich dort kein weiteres Vorkommen, ist mitte das erste. Der Aufwand bleibt logarithmisch, weil jeder Aufruf höchstens einen Selbstaufruf ausführt.
Ansatz: Ein früheres Vorkommen kann nur links von mitte liegen.
Weiter: Liefert die Suche links −1, ist der eigene Treffer der erste.
A9
Zweierpotenz-Falle
AFB III Trick

Ermittle die größte Zahl von Vergleichen mit a[mitte], die binSuche bei einer Reihung mit 1024 Elementen braucht.

Überlege selbst und trage das Ergebnis ein — Enter prüft direkt.
\(\lfloor \log_2 1024 \rfloor + 1 = 10 + 1 = 11\). Wer nur \(\log_2 1024 = 10\) rechnet, vergisst den letzten Vergleich im Bereich mit einem Element. Erst bei 1023 Elementen sind es 10.
Ansatz: Setze in \(\lfloor \log_2 n \rfloor + 1\) ein.
Weiter: Bei 1023 Elementen kommt man mit einem Vergleich weniger aus.
A10
Den Gipfel finden
AFB III

Eine Reihung steigt erst an und fällt dann, z. B. {1, 4, 9, 12, 7, 3}. Gesucht ist der Index des größten Elements. Entwickle eine rekursive Suche nach dem Muster der binären Suche.

Spiele den Ablauf Schritt für Schritt durch: Was passiert als Nächstes? Nur die richtige Karte bringt dich weiter.
    Dasselbe Muster wie die binäre Suche, aber mit einem anderen Vergleich: Nicht x entscheidet über die Hälfte, sondern die Richtung des Anstiegs. Für {1, 4, 9, 12, 7, 3} liefert die Methode Index 3.
    Ansatz: Überlege: Bergauf oder bergab an der Stelle mitte?
    Weiter: Achte darauf, dass mitte nicht wegfällt, wenn es selbst der Gipfel sein kann.