MINT lernen

Übungen: Binäre Suche

Zehn Übungen zur binären Suche — von Grenzen und Mitte bis zur absteigend sortierten Rangliste.

Dein Fortschritt:
0 / 0 Aufgaben
1

Übungsaufgaben

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

A1
Taugt die Reihung für die binäre Suche?
AFB I

Die binäre Suche aus dem Unterricht setzt eine aufsteigend sortierte Reihung voraus. Geben Sie für jede Reihung an, ob die Methode direkt verwendet werden kann.

Ziehen Sie jede Karte in den passenden Korb — oder wählen Sie sie mit Enter aus und drücken dann die Ziffer des Korbs (0 legt sie zurück).
1direkt geeignet
2absteigend: nur mit vertauschten Entscheidungen
3unsortiert: erst sortieren
Gleiche Werte nebeneinander stören die Sortierung nicht, auch negative Zahlen nicht, und eine Reihung mit einem Element ist trivial sortiert. Absteigend sortierte Reihungen gehen, wenn man „links weiter“ und „rechts weiter“ vertauscht. Schon ein Element an der falschen Stelle — wie 15 hinter 16 — macht die Entscheidung an der Mitte unzuverlässig.
Ansatz: Prüfen Sie von links nach rechts: Wird jeder Wert größer oder bleibt er gleich?
Weiter: Achten Sie auf das letzte Paar in der letzten Reihung.
A2
Stimmt's? — Grenzen und Mitte
AFB I

Es geht um die binäre Suche mit links, rechts und mitte = (links + rechts) / 2. Nennen Sie zu jeder Aussage, ob sie stimmt.

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

Die Mitte zählt nach dem Vergleich nicht mehr zum Suchbereich — deshalb immer mitte + 1 bzw. mitte − 1. Leer ist der Bereich erst bei links > rechts.
Ansatz: Rechnen Sie die Mitte mit ganzzahliger Division aus: Nachkommastellen fallen weg.
Weiter: Zählen Sie bei n = 64 die Indizes links und rechts von der Mitte 31.
A3
Kapitelanfänge im Buch
AFB I

Ein E-Book speichert die Seitenzahlen der Kapitelanfänge sortiert: int[] seite = {1, 14, 29, 37, 52, 68, 75, 91, 104};. Wenden Sie die binäre Suche für x = 91 an und tragen Sie für jeden Vergleich die Werte ein.

Füllen Sie alle Felder aus und prüfen Sie dann. Enter in einem Feld prüft ebenfalls. Wahrheitswerte als wahr oder falsch.
linksrechtsmitteseite[mitte]
Start mit links = 0, rechts = 8, Mitte 4 (52 < 91). Dann links = 5, Mitte (5 + 8) / 2 = 6 (75 < 91). Dann links = 7, Mitte (7 + 8) / 2 = 7 — Treffer nach 3 Vergleichen. Die lineare Suche hätte 8 gebraucht.
Ansatz: rechts startet bei Länge − 1 = 8.
Weiter: Nach „zu klein“ ändert sich nur links, und zwar auf mitte + 1.
A4
Halbieren in Zahlen
AFB II

Eine sortierte Reihung enthält 200 Artikelnummern. Berechnen Sie, wie schnell der Suchbereich der binären Suche schrumpft.

Rechnen Sie die Kette Schritt für Schritt: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
  1. Höchstens so viele Elemente bleiben nach 1 Vergleich ohne Treffer: Elemente
  2. Höchstens so viele Elemente bleiben nach 3 Vergleichen ohne Treffer: Elemente
  3. Höchstens so viele Vergleiche braucht die Suche insgesamt: Vergleiche
  4. Die Reihung wächst auf 400 Nummern. Höchstens so viele Vergleiche: Vergleiche
200 → 100 → 50 → 25 → 12 → 6 → 3 → 1: nach 7 Vergleichen ohne Treffer bleibt höchstens ein Element, der 8. Vergleich prüft es. Formel: \(\lfloor\log_2 200\rfloor + 1 = 7 + 1 = 8\), weil \(2^7 = 128 \le 200 < 256\). Doppelt so viele Daten kosten genau einen Vergleich mehr.
Ansatz: Jeder Vergleich ohne Treffer halbiert den Bereich (abgerundet bleibt die größere Hälfte).
Weiter: Suchen Sie die größte Zweierpotenz \(2^k \le 200\); dann sind es \(k + 1\) Vergleiche.
A5
Der Algorithmus in Schritten
AFB II

Die Schritte der binären Suche sind durcheinandergeraten. Stellen Sie den Algorithmus in der richtigen Reihenfolge dar.

Ziehen Sie die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.
1links ← 0 und rechts ← Länge − 1 setzen
2solange links ≤ rechts wiederhole:
3mitte ← (links + rechts) / 2 berechnen
4falls a[mitte] = x: gib mitte zurück
5sonst falls a[mitte] < x: links ← mitte + 1, sonst rechts ← mitte − 1
6nach der Schleife: gib −1 zurück
Die Mitte muss in jedem Durchlauf neu berechnet werden, gehört also in die Schleife. Die Rückgabe −1 steht nach der Schleife — erst wenn der Bereich leer ist, steht fest, dass x fehlt.
Ansatz: Was muss vor der Schleife feststehen, was in jedem Durchlauf neu passieren?
Weiter: Erst prüfen, ob die Mitte ein Treffer ist — dann erst eine Hälfte wählen.
A6
Die Suche hängt
AFB II

Diese Methode soll eine binäre Suche sein, liefert aber manchmal falsche Ergebnisse oder hält gar nicht an. Überprüfen Sie die Methode: Markieren Sie die zwei fehlerhaften Zeilen und korrigieren Sie sie.

static int suche(int[] a, int x) {
Klicken Sie die fehlerhaften Zeilen an — dann klappt ein Feld auf, in das Sie die richtige Zeile schreiben. Geprüft werden Auswahl und Korrekturen.
Zeile 1: Mit rechts = a.length kann mitte gleich der Länge werden, etwa bei einem Wert größer als alle — dann folgt ArrayIndexOutOfBoundsException. Zeile 5: Mit links = mitte bleibt z. B. bei links = 3, rechts = 4 die Mitte 3 für immer gleich — Endlosschleife.
Ansatz: Welche Indizes sind gültig, und schrumpft der Bereich in jedem Durchlauf wirklich?
Weiter: Spielen Sie a = {2, 4} mit x = 4 und mit x = 9 durch.
A7
Wie viele Vergleiche?
AFB II Mix

Hier treffen lineare und binäre Suche aufeinander. Ordnen Sie jeder Situation die Zahl der Vergleiche zu (alle Reihungen sind sortiert).

Klicken Sie links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
Die lineare Suche braucht Index + 1 bzw. n Vergleiche. Bei der binären Suche zählt der Weg über die Mitten: Bei n = 7 ist Index 3 die erste Mitte (1 Vergleich), Index 0 erreicht man über die Mitten 3, 1, 0 (3 Vergleiche). Ungünstigster Fall bei 50: \(\lfloor\log_2 50\rfloor + 1 = 5 + 1 = 6\).
Ansatz: Für die lineare Suche gilt: Treffer an Index i kostet i + 1 Vergleiche.
Weiter: Bei n = 7 sind die Mitten nacheinander 3, dann 1 oder 5, dann 0, 2, 4 oder 6.
A8
Radiosender suchen
AFB III

Ein Autoradio speichert die empfangbaren Frequenzen (gerundet in MHz) sortiert: {87, 89, 92, 94, 96, 99, 101, 103, 105, 107}. Gesucht wird 100. Analysieren Sie den Ablauf der binären Suche Schritt für Schritt.

Spielen Sie den Ablauf Schritt für Schritt durch: Was passiert als Nächstes? Nur die richtige Karte bringt Sie weiter.
    Auch ohne Treffer ist nach 4 Vergleichen Schluss — mehr als \(\lfloor\log_2 10\rfloor + 1 = 4\) sind nie nötig. Am Ende zeigen die Grenzen genau auf die Nachbarn 99 und 101, zwischen denen die 100 stehen müsste.
    Ansatz: Berechnen Sie jede Mitte mit ganzzahliger Division.
    Weiter: Ein Bereich mit einem Element (links = rechts) ist noch nicht leer.
    A9
    Welche Fünf?
    AFB III Trick

    Gegeben ist die sortierte Reihung int[] w = {2, 5, 5, 5, 5, 9, 11};. Bestimmen Sie den Rückgabewert von binaereSuche(w, 5).

    Überlegen Sie selbst und tragen Sie das Ergebnis ein — Enter prüft direkt.
    Die erste Mitte ist (0 + 6) / 2 = 3, und w[3] = 5 — sofort ein Treffer. Die binäre Suche liefert also Index 3, nicht das erste Vorkommen an Index 1 wie die lineare Suche. Bei doppelten Werten ist nur garantiert, dass ein passender Index geliefert wird.
    Ansatz: Rechnen Sie einfach die erste Mitte aus.
    Weiter: Die binäre Suche bricht beim ersten Treffer ab — egal, ob links davon noch dieselbe Zahl steht.
    A10
    Absteigend sortiert
    AFB III

    Eine Rangliste speichert Punktzahlen absteigend sortiert, z. B. {95, 80, 72, 60, 41}. Verändern Sie die binäre Suche so, dass sie für solche Reihungen korrekt arbeitet.

    Wählen Sie in jedem Menü den passenden Eintrag und prüfen Sie dann alle auf einmal.
    static int sucheAbsteigend(int[] a, int x) {
    int links = 0, rechts = ;
    while (links  rechts) {
        int mitte = (links + rechts) / 2;
        if (a[mitte] == x) return mitte;
        else if (a[mitte]  x) links = mitte + 1;
        else rechts = ;
    }
    return -1;
}
    Nur eine Entscheidung dreht sich um: In einer absteigenden Reihung steht rechts von der Mitte Kleineres. Ist a[mitte] > x, muss x also rechts liegen — links = mitte + 1. Grenzen, Schleifenbedingung und mitte - 1 bleiben wie gewohnt.
    Ansatz: Überlegen Sie an {95, 80, 72, 60, 41} mit x = 41: Die Mitte 72 ist größer — wo steht 41?
    Weiter: Alles außer der Richtungsentscheidung bleibt wie bei der aufsteigenden Suche.