Aufgaben: Lineare und binäre Suche

Gegeben ist das Feld [7, 3, 12, 5, 9, 1]. Führen Sie die lineare Suche nach dem Wert 5 durch. Geben Sie an, welche Positionen (Index ab 0) nacheinander geprüft werden und wie viele Vergleiche nötig sind.

Gegeben ist das sortierte Feld [2, 5, 8, 12, 16, 23, 38, 45] (Index 0 bis 7). Führen Sie die binäre Suche nach dem Wert 16 durch. Berechnen Sie die Mitte als $m = \lfloor (l + r) / 2 \rfloor$ (ganzzahlige Division). Geben Sie für jeden Schritt linke Grenze, rechte Grenze, Mitte und den Vergleich an.

Erklären Sie, warum die binäre Suche nur in einem sortierten Feld funktioniert, und nennen Sie ein Alltagsbeispiel (z. B. Telefonbuch der Stadt Essen), das dem Verfahren ähnelt.

Schreiben Sie in Java eine Methode int linearSuche(int[] a, int x), die den Index des ersten Vorkommens von x zurückgibt oder −1, falls x nicht vorkommt. Testen Sie sie gedanklich mit a = {4, 8, 15, 16} und x = 15 sowie x = 3.

Gegeben ist das sortierte Feld [3, 9, 14, 21, 27, 33, 40, 52, 61, 70, 85] (Index 0 bis 10). Für die Mitte gilt $m = \lfloor (l + r) / 2 \rfloor$ (ganzzahlige Division).

1. a) Führen Sie die binäre Suche nach 52 durch und protokollieren Sie jeden Schritt.

1. b) Führen Sie die binäre Suche nach 30 durch und geben Sie an, wann und warum das Verfahren abbricht.

1. c) Vergleichen Sie die Anzahl der Vergleiche mit der linearen Suche nach 52.

Eine Stadtbücherei in Leipzig hat 1.000 nach Nummern sortierte Bücher.

1. a) Wie viele Vergleiche braucht die lineare Suche im ungünstigsten Fall?

1. b) Wie viele Vergleiche braucht die binäre Suche höchstens? (Hinweis zur Methode: Wie oft kann man 1.000 halbieren, bis ein Element übrig bleibt?)

1. c) Wie ändert sich die höchste Zahl an Vergleichen der binären Suche, wenn sich die Bücherzahl verdoppelt?

Schreiben Sie in Java eine Methode int binaereSuche(int[] a, int x) für ein aufsteigend sortiertes Feld, die den Index von x zurückgibt, falls x im Feld vorkommt, und sonst -1. Beachten Sie dabei die Berechnung der Mitte und die Abbruchbedingung. Begründen Sie mit einer Schleifeninvariante, warum die Methode korrekt ist.

Eine Datenbank enthält $n = 1.000.000$ sortierte Einträge. Ein Zugriff dauert 0,002 ms.

1. a) Berechnen Sie die höchste Zahl an Vergleichen und die Gesamtzeit für die lineare und für die binäre Suche im ungünstigsten Fall.

1. b) Die Daten sind unsortiert. Sortieren kostet einmalig etwa $n \cdot \log_2 n$ Zugriffe (rechnen Sie hier mit $\log_2 n \approx 19{,}93$). Ab wie vielen Suchanfragen lohnt sich das Sortieren mit anschließender binärer Suche im Vergleich zur linearen Suche im Worst Case? Runden Sie sinnvoll.

Beurteilen Sie, welches Suchverfahren Sie in folgenden Situationen wählen, und begründen Sie:

1. a) Eine Liste mit 20 Namen, die sich ständig ändert.

1. b) Ein sortiertes Archiv mit 50 Millionen Datensätzen, das selten geändert wird.

1. c) Ein sortiertes Feld, in dem der gesuchte Wert mit hoher Wahrscheinlichkeit an den ersten Stellen steht.