Dein Fortschritt:
0 / 0 Aufgaben
1
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.
Reihung plz (Länge 12)
plz18055020095124103228195330159434117538100644135750667860311970173108033111
- 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)
Voraussetzung der binären Suche nennen und am Beispiel prüfen.
Hinweis zu Aufgabe b)
Die Tabelle endet bei einem Treffer oder sobald
links > rechts gilt.Hinweis zu Aufgabe c)
Formel \(\lfloor\log_2 n\rfloor + 1\); die größte Zweierpotenz unter 8 200 ist \(2^{13} = 8192\).Ermitteln: Ergebnis finden und formulieren.
Hinweis zu Aufgabe d)
Zwei Grenzen, eine Schleife mit der Bedingung
links <= rechts, drei Fälle.