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.
- 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)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Der Suchbereich umfasst anfangs alle Indizes (links = 0, rechts = Länge − 1). In jedem Schritt wird das mittlere Element mitte = (links + rechts) / 2 mit x verglichen: bei Gleichheit wird mitte zurückgegeben; ist tickets[mitte] kleiner, wird rechts weitergesucht (links ← mitte + 1), sonst links (rechts ← mitte − 1). Ist der Bereich leer (links > rechts), wird −1 geliefert. Voraussetzung: Die Reihung ist aufsteigend sortiert.
Erwartungshorizont zu Aufgabe b)
| links | rechts | mitte | tickets[mitte] | Entscheidung |
|---|---|---|---|---|
| 0 | 15 | 7 | 3925 | < x → links ← 8 |
| 8 | 15 | 11 | 5613 | > x → rechts ← 10 |
| 8 | 10 | 9 | 4876 | < x → links ← 10 |
| 10 | 10 | 10 | 5270 | gefunden → 10 |
Rückgabe 10 nach 4 Vergleichen (linear wären es 11). Für 5100 sind die ersten drei Zeilen identisch; in Zeile 4 gilt 5270 > 5100, also rechts ← 9. Wegen links = 10 > rechts = 9 endet die Suche mit −1 — ebenfalls nach 4 Vergleichen.
Erwartungshorizont zu Aufgabe c)
Jeder erfolglose Vergleich schließt die Mitte und eine Hälfte aus; übrig bleiben höchstens \(\lfloor n/2 \rfloor\) Elemente: 16 → 8 → 4 → 2 → 1. Nach vier erfolglosen Vergleichen ist höchstens ein Element übrig, der fünfte Vergleich entscheidet endgültig. Allgemein: \(\lfloor\log_2 16\rfloor + 1 = 5\).
Erwartungshorizont zu Aufgabe d)
Binär: \(\lfloor\log_2 60\,000\rfloor + 1 = 15 + 1 = 16\) Vergleiche; linear: 60 000. Pro Stunde also höchstens 32 000 gegen 120 Millionen Vergleiche — die binäre Suche ist rund 3750-mal sparsamer; auch bei doppelt so vielen Tickets käme nur ein Vergleich hinzu.
Messwerte über einer Schwelle
16 BEAFB II–IIIEin Labor speichert Messwerte (in µg/l) aufsteigend sortiert in einer Reihung a; Werte können mehrfach vorkommen. Für Auswertungen wird der abgebildete Algorithmus ersterAb(a, g) verwendet. Beispiel:
- Analysieren Sie den Algorithmus, indem Sie ihn für das Beispiel mit
g = 21in einer Tracetabelle durchlaufen. Geben Sie an, was der Rückgabewert allgemein bedeutet — auch fürg = 40. (5 BE) - Begründen Sie, dass der Algorithmus für jede Eingabe endet und höchstens \(\lfloor\log_2 n\rfloor + 1\) Schleifendurchläufe benötigt. (3 BE)
- Implementieren Sie eine Methode
static int anzahlImBereich(int[] a, int von, int bis), die zurückgibt, wie viele Wertewmitvon ≤ w ≤ bisinastehen. Sie dürfen eine Java-MethodeersterAbals gegeben voraussetzen. Geben Sie das Ergebnis für das Beispiel mitvon = 15,bis = 21an. (4 BE) - Beurteilen Sie, ob
anzahlImBereichoder ein einfaches Durchzählen aller Werte besser geeignet ist, wenn eine Messreihe mit \(10^6\) Werten vorliegt und täglich 10 000 Bereichsabfragen gestellt werden. (4 BE)
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
bis?Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
| links | rechts | mitte | a[mitte] | a[mitte] ≥ 21 | erg |
|---|---|---|---|---|---|
| 0 | 9 | 4 | 21 | wahr | 4 |
| 0 | 3 | 1 | 15 | falsch | 4 |
| 2 | 3 | 2 | 15 | falsch | 4 |
| 3 | 3 | 3 | 18 | falsch | 4 |
Danach gilt links = 4 > rechts = 3; Rückgabe 4. Der Algorithmus liefert den kleinsten Index mit a[i] ≥ g, also die Position des ersten Werts ab der Schwelle. Gibt es keinen solchen Wert (z. B. g = 40), bleibt erg bei der Länge 10 — die Stelle, an der g einzufügen wäre.
Erwartungshorizont zu Aufgabe b)
In jedem Durchlauf wird entweder rechts auf mitte − 1 oder links auf mitte + 1 gesetzt; die Mitte liegt im Bereich, also verliert er mindestens ein Element und behält höchstens die größere Hälfte \(\lfloor m/2 \rfloor\) von \(m\) Elementen. Die Anzahl sinkt streng, deshalb endet die Schleife. Wie bei der binären Suche sind nach \(\lfloor\log_2 n\rfloor\) Durchläufen höchstens ein Element und nach einem weiteren keines mehr übrig.
Erwartungshorizont zu Aufgabe c)
static int anzahlImBereich(int[] a, int von, int bis) {
// Werte sind ganzzahlig: "größer als bis" heißt "mindestens bis + 1"
return ersterAb(a, bis + 1) - ersterAb(a, von);
}Beispiel: ersterAb(a, 22) = 7 und ersterAb(a, 15) = 1, also 6 Werte (15, 15, 18, 21, 21, 21).
Erwartungshorizont zu Aufgabe d)
Durchzählen: je Abfrage \(10^6\) Vergleiche, am Tag \(10^{10}\). anzahlImBereich: zwei Aufrufe mit je höchstens \(\lfloor\log_2 10^6\rfloor + 1 = 20\) Durchläufen, also etwa 40 je Abfrage und 400 000 am Tag — um den Faktor 25 000 weniger. Voraussetzung ist die Sortierung, die hier gegeben ist; kämen ständig neue Werte hinzu, müsste die Sortierung erhalten werden (einfügen statt anhängen). Fazit: Für viele Abfragen auf einer sortierten Messreihe ist anzahlImBereich klar vorzuziehen; das Durchzählen lohnt nur bei unsortierten Daten und sehr wenigen Abfragen.