Dreißig Übungen zum Vergleich von linearer und binärer 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
Das Stadtarchiv
AFB I
Das Stadtarchiv verwaltet 100 000 Karteikarten, die nach Aktenzeichen sortiert in einer Reihung liegen. Wenden Sie die Formel \(\lfloor\log_2 n\rfloor + 1\) auf \(n = 100\,000\) an und stellen Sie die Höchstzahl der Vergleiche der binären Suche mit dem Regler ein.
Schieben Sie den Regler auf Ihre Schätzung — Pfeiltasten bewegen ihn feiner. Nach dem Prüfen sehen Sie den Trefferbereich.
0 Vergleiche30 Vergleiche
Es gilt \(2^{16} = 65\,536 \le 100\,000 < 131\,072 = 2^{17}\), also \(\lfloor\log_2 100\,000\rfloor = 16\) und mit dem letzten Vergleich höchstens 17 Vergleiche.
Suchen Sie die größte Zweierpotenz, die nicht größer als 100 000 ist.
\(2^{16} = 65\,536\) passt noch, \(2^{17} = 131\,072\) ist zu groß: Der Logarithmus wird auf 16 abgerundet, danach kommt 1 dazu.
A2
Der Suchbaum der Regalreihe
AFB IIIMix
In einem Hochregallager stehen die Nummern von 15 Fächern aufsteigend sortiert in einer Reihung (Index 0 bis 14). Die binäre Suche berechnet die Mitte mit mitte = (links + rechts) / 2 und ganzzahliger Division. Entwerfen Sie den Suchbaum als Bild: Jede Zeile ist ein Index, jede Spalte ein Vergleich. Malen Sie in Spalte k alle Indizes an, die beim k-ten Vergleich für irgendeinen Suchwert die Mitte sein können.
Wählen Sie die Farbe „Mitte“ und klicken Sie die Felder an — ein zweiter Klick auf ein gemaltes Feld leert es wieder. Jede Zeile ist ein Index (0 bis 14, von oben nach unten), jede Spalte ein Vergleich. Mit der Tastatur: Tab ins Raster, Pfeiltasten wandern, Enter malt, Entf leert.
1. Vergleich2. Vergleich3. Vergleich4. Vergleich
Erster Vergleich: \((0+14)/2 = 7\). Danach bleiben 0 bis 6 und 8 bis 14, deren Mitten \(3\) und \(11\) sind; dann \(1, 5, 9, 13\) und zuletzt die acht übrigen geraden Indizes. Die Spalten enthalten 1, 2, 4 und 8 Felder — jede Ebene verdoppelt, und bei 15 Elementen ist nach höchstens 4 Vergleichen Schluss.
Berechnen Sie zuerst die Mitte für den Suchbereich 0 bis 14. Danach teilt sich der Bereich in eine linke und eine rechte Hälfte.
Aus 0 bis 6 wird die Mitte 3, aus 8 bis 14 die Mitte 11. So verdoppelt sich die Zahl der möglichen Mitten in jeder Spalte: 1, 2, 4, 8.
A3
Fehlersuche im Referat
AFB III
Aus einem Referat über Suchverfahren stammen die folgenden Sätze. Überprüfen Sie die Aussagen und markieren Sie die drei falschen.
In diesem Text stecken Fehler. Klicken Sie genau die falschen Zeilen an — die richtigen bleiben stehen.
Am häufigsten falsch eingeschätzt wird die Größenordnung: \(\log_2\) einer Million ist rund 20, nicht die Wurzel 1 000. Und die Schnelligkeit der binären Suche gilt nur, wenn die Sortierung schon vorliegt — ihre Kosten muss man sonst mitrechnen.
Ansatz: Drei Sätze sind falsch — prüfen Sie Zahlen, Voraussetzungen und Speicher.
