Dein Fortschritt:
0 / 0 Aufgaben
1
Ticketkontrolle beim Festival
13 BEAFB I–IIAm Einlass eines Festivals wird jedes Ticket gescannt. Die gültigen Ticketnummern stehen aufsteigend sortiert in der Reihung tickets. Geprüft wird mit der binären Suche aus dem Unterricht, die den Index oder −1 liefert.
Ausschnitt: Reihung tickets (Länge 16)
tickets10420118711530222153264843071533906392574410848769527010561311604412658113712914776015
- Beschreiben Sie das Vorgehen der binären Suche und nennen Sie ihre Voraussetzung. (3 BE)
- Stellen Sie die Suche nach
x = 5270in einer Tracetabelle mit den Spaltenlinks,rechts,mitteundtickets[mitte]dar. Geben Sie an, wie sich der Ablauf fürx = 5100unterscheidet. (4 BE) - Erläutern Sie, warum die binäre Suche für die 16 Tickets höchstens 5 Vergleiche benötigt. (3 BE)
- Schätzen Sie ab, wie viele Vergleiche eine Prüfung bei 60 000 Tickets im ungünstigsten Fall mit binärer bzw. linearer Suche braucht und was das bei 2000 Scans pro Stunde bedeutet. (3 BE)
Hinweise
Hinweis zu Aufgabe a)
Suchbereich, Mitte, Vergleich, Verkleinern, Abbruch — in dieser Reihenfolge.
Hinweis zu Aufgabe b)
Die erste Mitte ist (0 + 15) / 2 = 7. Bei 5100 verlaufen die ersten drei Zeilen gleich.
Hinweis zu Aufgabe c)
Wie viele Elemente bleiben nach jedem erfolglosen Vergleich höchstens übrig?
Hinweis zu Aufgabe d)
\(2^{15} = 32\,768\), \(2^{16} = 65\,536\).