MINT üben

Binäre Suche

Dreißig Übungen zur binären Suche — von AFB I bis AFB III.

Ihr Fortschritt:
0 / 0 Aufgaben
1

Übungsaufgaben

Dreißig Übungen in gemischter Reihenfolge — Sie klicken, ziehen, ordnen, rechnen und knobeln. Jede Übung gibt Ihnen sofort eine Rückmeldung, und zu jeder Aufgabe gibt es zwei gestufte Tipps: Der erste zeigt die Richtung, der zweite den entscheidenden Schritt. Die Chips zeigen das Anforderungsniveau: AFB I heißt wiedergeben und direkt anwenden, AFB II selbst entscheiden und verknüpfen, AFB III begründen, beurteilen oder eine Falle durchschauen. Aufgaben mit dem Chip Mix verbinden Wissen aus früheren Unterkapiteln, bei Trick steckt eine Falle drin. Fahren Sie über ein unterstrichenes Arbeitswort, sehen Sie, was es genau von Ihnen verlangt.

A1
Der nächste Schritt der Suche
AFB I

Ein Verein speichert die Trikotnummern seines Kaders aufsteigend sortiert: nr = {8, 15, 23, 31, 42, 50, 57, 63, 71, 88}. Gesucht wird x = 57; die binäre Suche läuft gerade mit links = 5 und rechts = 9. Beschreiben Sie mit dem Entscheidungsbaum, wie es nach dem nächsten Vergleich weitergeht: Beantworten Sie die Fragen für diesen Zustand.

Beantworten Sie die Fragen des Entscheidungsbaums mit Ja oder Nein und schauen Sie, wo Sie herauskommen.
    Mit links = 5 und rechts = 9 ist mitte = (5 + 9) / 2 = 7 und nr[7] = 63. Der Bereich ist nicht leer, 63 ist nicht 57 und auch nicht kleiner als 57 — also liegt 57 links von der Mitte, und es gilt rechts ← 7 − 1 = 6.
    Berechnen Sie zuerst die Mitte aus den beiden Grenzen und lesen Sie das Element an dieser Stelle ab.
    Vergleichen Sie dieses Element mit 57: Ist es größer als der Suchwert, liegt 57 in der linken Hälfte.
    A2
    Welche Fünf?
    AFB III

    Gegeben ist die sortierte Reihung int[] w = {2, 5, 5, 5, 5, 9, 11};. Entscheiden Sie, welchen Rückgabewert der Aufruf binaereSuche(w, 5) liefert.

    Ü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.
    A3
    Die Suche in Unordnung
    AFB II

    Ein Sensor hat sieben Werte in der Reihenfolge der Messung gespeichert; sie sind nicht sortiert: p = {12, 5, 20, 9, 31, 17, 40}. Die Methode binaereSuche wird trotzdem verwendet. Untersuchen Sie jeden Aufruf und kreuzen Sie an, was geschieht: Sie findet den Wert, sie verfehlt ihn (−1, obwohl er in p steht) oder der Wert fehlt wirklich (−1 ist richtig).

    Setzen Sie in jeder Zeile das passende Kreuz — hier ist es genau eins pro Zeile. Enter setzt und löscht.
    Aufruffindetverfehltfehlt
    binaereSuche(p, 9)
    binaereSuche(p, 12)
    binaereSuche(p, 7)
    binaereSuche(p, 20)
    binaereSuche(p, 17)
    binaereSuche(p, 33)
    Die erste Mitte ist Index 3 mit dem Wert 9: Die Suche nach 9 trifft sofort. Bei 12 und 20 führt der Vergleich mit 9 bzw. mit 17 in die falsche Hälfte — beide Werte stehen in der Reihung, werden aber nie erreicht (Ergebnis −1). Die Werte 7 und 33 kommen tatsächlich nicht vor. Die 17 liegt zufällig auf einer Mitte (Index 5).
    Spielen Sie jeden Aufruf mit links = 0 und rechts = 6 durch und merken Sie sich, welche Mitten verglichen werden.
    Steht der Wert in p, die Suche endet aber mit −1, wurde er verfehlt. Das passiert genau dann, wenn eine Entscheidung ihn in die Hälfte ohne ihn schickt.