Postleitzahlen-Verzeichnis
AFB I–IIEin Versandhändler speichert die Postleitzahlen der Städte, in die er am selben Tag liefert, aufsteigend sortiert in der Reihung plz. Bei jeder Bestellung wird mit der binären Suche geprüft, ob die Postleitzahl x der Lieferadresse enthalten ist. Die Mitte wird mit mitte ← (links + rechts) / 2 (ganzzahlige Division) bestimmt.
- Beschreiben Sie das Prinzip der binären Suche und begründen Sie, warum sie hier anwendbar ist.
- Stellen Sie die Suche nach
x = 60311und nachx = 26000jeweils in einer Tracetabelle mit den Spaltenlinks,rechts,mitte,plz[mitte]dar. Geben Sie Rückgabewert und Zahl der Vergleiche an. - Ermitteln Sie die höchstens nötige Zahl der Vergleiche für diese Reihung und für ein vollständiges Verzeichnis mit etwa 8 200 Postleitzahlen. Vergleichen Sie jeweils mit der linearen Suche.
- Implementieren Sie die binäre Suche als Java-Methode
static int binaereSuche(int[] a, int x).
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
links > rechts gilt.Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
links <= rechts, drei Fälle.Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Man vergleicht x mit dem mittleren Element des Suchbereichs. Bei Gleichheit ist die Suche beendet; ist das mittlere Element kleiner, sucht man nur noch rechts davon weiter, sonst nur links. So halbiert jeder Vergleich den Suchbereich, bis x gefunden oder der Bereich leer ist (Rückgabe −1). Anwendbar, weil plz aufsteigend sortiert ist: Links der Mitte stehen nur kleinere, rechts nur größere Werte.
Erwartungshorizont zu Aufgabe b)
| links | rechts | mitte | plz[mitte] |
|---|---|---|---|
| 0 | 11 | 5 | 34117 |
| 6 | 11 | 8 | 50667 |
| 9 | 11 | 10 | 70173 |
| 9 | 9 | 9 | 60311 |
Rückgabe 9 nach 4 Vergleichen.
| links | rechts | mitte | plz[mitte] |
|---|---|---|---|
| 0 | 11 | 5 | 34117 |
| 0 | 4 | 2 | 24103 |
| 3 | 4 | 3 | 28195 |
| 3 | 2 | — | — |
Nach dem dritten Vergleich gilt links = 3 > rechts = 2: Rückgabe −1 nach 3 Vergleichen.
Erwartungshorizont zu Aufgabe c)
\(n = 12\): \(\lfloor\log_2 12\rfloor + 1 = 3 + 1 = 4\) Vergleiche (lineare Suche: bis zu 12). \(n = 8\,200\): Wegen \(2^{13} = 8\,192 \le 8\,200 < 2^{14}\) ist \(\lfloor\log_2 8\,200\rfloor = 13\), also höchstens 14 Vergleiche — die lineare Suche braucht im ungünstigsten Fall 8 200.
Erwartungshorizont zu Aufgabe d)
static int binaereSuche(int[] a, int x) {
int links = 0;
int rechts = a.length - 1;
while (links <= rechts) {
int mitte = (links + rechts) / 2;
if (a[mitte] == x) {
return mitte;
} else if (a[mitte] < x) {
links = mitte + 1;
} else {
rechts = mitte - 1;
}
}
return -1;
}Blitzortung
AFB II–IIIEin Blitzortungssystem speichert für ein Gewitter die Zeitpunkte der Einschläge in Sekunden nach Beginn der Messung, aufsteigend sortiert. Mehrere Einschläge können auf dieselbe Sekunde fallen. Für die Auswertung wird der Index des ersten Einschlags zum Zeitpunkt t oder später gebraucht. Dazu dient der abgebildete Algorithmus.
Beispiel: zeit = {3, 8, 15, 21, 21, 21, 30, 42, 50}.
- Analysieren Sie den Algorithmus für das Beispiel und
t = 21mit einer Tracetabelle. Geben Sie den Rückgabewert, die Zahl der Vergleichezeit[mitte] ≥ tund die Bedeutung des Ergebnisses an. - Erläutern Sie, warum der Algorithmus nach einem Treffer nicht abbricht, sondern links weitersucht, und welche Rolle die Variable
ergebnisspielt. - Vergleichen Sie
ersterAb(zeit, 21)mit dem AufrufbinaereSuche(zeit, 21)der üblichen binären Suche hinsichtlich Ergebnis und Zahl der Vergleiche. - Eine Mitschülerin meint: „Weil
ersterAbimmer weiterläuft, bis der Bereich leer ist, ist es nicht schneller als eine lineare Suche.“ Beurteilen Sie diese Aussage.
Hinweise
Hinweis zu Aufgabe a)
links, rechts, mitte, zeit[mitte], Vergleichsergebnis, ergebnis.Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
ersterAb?Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
| links | rechts | mitte | zeit[mitte] | ≥ 21 | ergebnis |
|---|---|---|---|---|---|
| 0 | 8 | 4 | 21 | wahr | 4 |
| 0 | 3 | 1 | 8 | falsch | 4 |
| 2 | 3 | 2 | 15 | falsch | 4 |
| 3 | 3 | 3 | 21 | wahr | 3 |
| 3 | 2 | — | — | — | 3 |
Rückgabe 3 nach 4 Vergleichen. Bedeutung: Index 3 ist der erste Einschlag zum Zeitpunkt 21 oder später — genauer: der kleinste Index mit zeit[i] ≥ t; gibt es keinen, liefert der Algorithmus −1.
Erwartungshorizont zu Aufgabe b)
Ein Treffer an der Mitte zeigt nur, dass hier ein Wert ≥ t steht. Weil gleiche Zeitpunkte vorkommen können, kann weiter links ein noch früherer passender Einschlag stehen. ergebnis merkt sich den bisher kleinsten passenden Index; die Suche geht in der linken Hälfte weiter (rechts ← mitte − 1). Findet sie dort nichts mehr, bleibt der gemerkte Index richtig. Ist zeit[mitte] < t, kann links davon nichts Passendes stehen — links ← mitte + 1.
Erwartungshorizont zu Aufgabe c)
binaereSuche(zeit, 21) trifft sofort an der ersten Mitte (Index 4) und liefert 4 nach 1 Vergleich — ein korrekter Index eines Werts 21, aber nicht der erste. ersterAb liefert 3 nach 4 Vergleichen. Die übliche Suche ist hier schneller, beantwortet aber eine andere Frage (irgendein Vorkommen statt erstes). Außerdem liefert sie −1, wenn t selbst nicht vorkommt (z. B. t = 25), während ersterAb dann den nächstspäteren Einschlag findet (Index 6).
Erwartungshorizont zu Aufgabe d)
Die Aussage ist falsch. ersterAb läuft zwar immer bis links > rechts, halbiert den Bereich aber in jedem Durchlauf, weil mitte stets ausgeschlossen wird. Damit sind es höchstens \(\lfloor\log_2 n\rfloor + 1\) Vergleiche (hier 4 bei \(n = 9\)), bei einer Million Einschlägen höchstens 20 statt bis zu einer Million bei der linearen Suche. Richtig ist nur: Der beste Fall mit einem Vergleich entfällt; die Zahl der Vergleiche ist fast immer die maximale.