MINT lernen

Übungen: Lineare und binäre Suche

Zehn Übungen zur linearen und binären Suche — vom Nachvollziehen der Mitten bis zur Suche nach dem ersten Vorkommen.

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
Was die binäre Suche braucht
AFB I

Sie vergleichen die lineare und die binäre Suche auf einer Reihung der Länge n. Geben Sie alle Aussagen an, die zutreffen.

Mehrere Antworten sind richtig. Markieren Sie alle zutreffenden und klicken Sie dann auf „Auswahl prüfen“.
Steht x an Index 0, findet die lineare Suche es nach einem Vergleich — die binäre erst nach mehreren. Die Schleife läuft bei links = rechts noch einmal (ein Element ist übrig); Schluss ist erst bei links > rechts. Bei doppelten Werten trifft die binäre Suche irgendein Vorkommen.
Ansatz: Überlegen Sie bei jeder Aussage, ob es ein Gegenbeispiel gibt.
Weiter: Drei Aussagen sind falsch. Denken Sie an einen Wert ganz vorn und an einen Bereich mit genau einem Element.
A2
Stimmt's? — Preisliste
AFB I

Ein Online-Shop speichert Preise in Euro aufsteigend: int[] preis = {12, 19, 23, 31, 38, 44, 50, 57, 63};. Wenden Sie die binäre Suche gedanklich an und entscheiden Sie bei 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

Merken Sie sich den Ablauf: Mitte berechnen, vergleichen, eine Grenze auf mitte ± 1 setzen.
Ansatz: Berechnen Sie jede Mitte mit ganzzahliger Division: (links + rechts) / 2.
Weiter: Die Mitte ist nach dem Vergleich erledigt — deshalb mitte + 1 bzw. mitte − 1.
A3
Tracetabelle Wanderkarte
AFB I

Die Kilometersteine eines Wanderwegs sind sortiert gespeichert: int[] km = {3, 7, 11, 16, 20, 25, 29, 34, 38, 42, 47, 51};. Stellen Sie den Ablauf von binaereSuche(km, 16) in der Tracetabelle dar.

Füllen Sie alle Felder aus und prüfen Sie dann. Enter in einem Feld prüft ebenfalls.
Vergleichlinksrechtsmittekm[mitte]
1011
20
3416
Rückgabe
25 > 16: rechts ← 4. 11 < 16: links ← 3. (3 + 4) / 2 = 3, und km[3] = 16 — Treffer nach drei Vergleichen. Linear wären es vier gewesen.
Ansatz: Beginnen Sie mit links = 0 und rechts = Länge − 1 = 11.
Weiter: Ist km[mitte] zu groß, wandert rechts; ist es zu klein, wandert links.
A4
Wie viele Blicke höchstens?
AFB II

Für sortierte Reihungen verschiedener Länge wird der ungünstigste Fall der binären Suche gesucht. Berechnen Sie die Werte mit \(\lfloor\log_2 n\rfloor + 1\).

Rechnen Sie die Kette Schritt für Schritt: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
  1. n = 100: Vergleiche
  2. n = 5000: Vergleiche
  3. lineare Suche bei n = 5000 im ungünstigsten Fall: Vergleiche
  4. größtes n, bei dem die binäre Suche höchstens 12 Vergleiche braucht: Elemente
\(2^6 = 64 \le 100 < 128\) ergibt 6 + 1 = 7; \(2^{12} = 4096 \le 5000\) ergibt 13. Für höchstens 12 Vergleiche muss \(\lfloor\log_2 n\rfloor \le 11\) sein, also \(n < 2^{12}\): höchstens 4095 Elemente.
Ansatz: Suchen Sie die größte Zweierpotenz \(2^k \le n\); dann ist \(k = \lfloor\log_2 n\rfloor\).
Weiter: Für die letzte Zeile: Ab welcher Länge kommt ein 13. Vergleich hinzu?
A5
Enthalten oder nicht?
AFB II

Eine Methode soll mit der binären Suche prüfen, ob x in der sortierten Reihung a vorkommt. Erstellen Sie aus den Zeilen eine korrekte Methode, indem Sie sie ordnen.

Ziehen Sie die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.
1static boolean istEnthalten(int[] a, int x) {
2int links = 0, rechts = a.length - 1;
3while (links <= rechts) {
4int mitte = (links + rechts) / 2;
5if (a[mitte] == x) return true;
6if (a[mitte] < x) links = mitte + 1; else rechts = mitte - 1;
7} // Ende der Schleife
8return false; }
Die Mitte muss in jedem Durchlauf neu berechnet werden, deshalb steht sie in der Schleife. return false kommt erst, wenn der Bereich leer ist — also nach der Schleife.
Ansatz: Grenzen einmal vor der Schleife, Mitte in jedem Durchlauf.
Weiter: Erst prüfen, ob die Mitte ein Treffer ist, dann die Grenze verschieben.
A6
Ausdruck und Wert
AFB II Mix

Gegeben ist die sortierte Reihung int[] z = {2, 5, 8, 13, 21, 34, 55}; und die Methoden aus dem Unterricht. Ordnen Sie jedem Ausdruck seinen Wert zu.

Klicken Sie links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
Zwei Ausdrücke liefern einen Index, einer ein Element, einer die Länge, einer das Signal „fehlt“. z.length / 2 ist ganzzahlig 3, also z[3] = 13. z[1] ist 5 und steht an Index 1.
Ansatz: Unterscheiden Sie: Liefert der Ausdruck einen Index oder einen gespeicherten Wert?
Weiter: Werten Sie den inneren Ausdruck z[1] zuerst aus.
A7
Drei Fehler in der Mitte
AFB II

Die folgende binäre Suche soll wie im Unterricht mit dem Bereich links … rechts (beide Grenzen eingeschlossen) arbeiten. Überprüfen Sie den Code und markieren Sie genau die fehlerhaften Zeilen.

In diesem Code stecken Fehler. Klicken Sie genau die falschen Zeilen an — die richtigen müssen stehen bleiben.
Alle drei Fehler betreffen Grenzen: Startwert, Schleifenbedingung und Verschiebung. Wer sie findet, prüft immer die Randfälle „ein Element“ und „zwei Elemente“.
Ansatz: Prüfen Sie jede Grenze: Welcher Index ist der letzte gültige?
Weiter: Spielen Sie den Fall mit zwei Elementen durch: Wird der Bereich in jedem Durchlauf kleiner?
A8
Welche Suche passt?
AFB III

Nicht jede Situation verlangt dasselbe Verfahren. Entscheiden Sie für jede Situation, welches Vorgehen am effizientesten ist.

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).
1Lineare Suche
2Binäre Suche
3Erst sortieren, dann binär suchen
Die Liste nach Anmeldezeit ist sortiert — aber nicht nach dem Namen. Für die binäre Suche muss die Reihung nach genau dem Suchschlüssel sortiert sein. Sortieren lohnt sich nur, wenn danach sehr oft gesucht wird.
Ansatz: Fragen Sie zuerst: Ist die Reihung nach dem gesuchten Merkmal sortiert?
Weiter: Wenn nicht: Wird so oft gesucht, dass sich das Sortieren auszahlt?
A9
Binär, aber unsortiert
AFB III Trick

Jemand ruft die binäre Suche aus dem Unterricht versehentlich auf einer unsortierten Reihung auf: int[] u = {9, 4, 7, 1, 8, 3, 6};. Bestimmen Sie den Rückgabewert von binaereSuche(u, 7).

Überlegen Sie selbst und tragen Sie das Ergebnis ein — Enter prüft direkt.
Mitten 3 (1 < 7), 5 (3 < 7), 6 (6 < 7) — danach ist links = 7 > rechts = 6. Die Methode liefert −1, obwohl 7 an Index 2 steht. Sie stürzt nicht ab, sondern irrt still.
Ansatz: Führen Sie den Algorithmus stur aus — auch wenn das Ergebnis seltsam ist.
Weiter: Nach dem ersten Vergleich wird der ganze linke Teil ausgeschlossen, in dem die 7 steht.
A10
Das erste Vorkommen
AFB III

Die binäre Suche liefert bei doppelten Werten irgendein Vorkommen. Sie soll so verändert werden, dass sie den kleinsten Index mit a[i] == x liefert und trotzdem höchstens \(\lfloor\log_2 n\rfloor + 1\) Durchläufe braucht. Verändern Sie die Methode, indem Sie die Lücken füllen.

Wählen Sie in jedem Menü den passenden Eintrag und prüfen Sie dann alle auf einmal.
static int ersteStelle(int[] a, int x) {
    int links = 0, rechts = a.length - 1, erg = -1;
    while (links <= rechts) {
        int mitte = (links + rechts) / 2;
        if (a[mitte]  x) {
            if (a[mitte] == x) erg = ;
            rechts = ;
        } else {
            links = ;
        }
    }
    return erg;
}
Ein Treffer wird nur vorgemerkt (erg = mitte), dann sucht die Methode links davon weiter (rechts = mitte - 1) — dort könnte ein früheres Vorkommen stehen. Am Ende steht in erg der kleinste Treffer oder −1.
Ansatz: Bei einem Treffer dürfen Sie nicht sofort aufhören: Links könnte noch ein gleicher Wert stehen.
Weiter: Behandeln Sie „gleich“ wie „zu groß“: weiter in der linken Hälfte suchen, den Treffer aber merken.