Lineare und binäre Suche
Die Stadtbücherei in Leipzig hat 1.000 Bücher, die nach Nummern sortiert im Regal stehen. Du suchst Buch Nr. 713. Gehst du jedes Buch von vorn durch, oder gibt es einen cleveren Weg? Am Ende der Seite weißt du, wie viele Schritte du im schlimmsten Fall brauchst.
Lineare Suche
Du hast ein Feld (Array) a und suchst einen Wert x. Die einfachste Idee: Du prüfst der Reihe nach jede Position, beginnend bei Index 0. Sobald du x findest, gibst du den Index zurück. Erreichst du das Ende, ohne x zu finden, gibst du −1 zurück (−1 ist kein gültiger Index und zeigt „nicht gefunden“ an).
Diese lineare Suche funktioniert bei jedem Feld, sortiert oder nicht.
int linearSuche(int[] a, int x) {
for (int i = 0; i < a.length; i++) {
if (a[i] == x) {
return i;
}
}
return -1;
}
Wie viele Vergleiche sind nötig? Im besten Fall einer (der Wert steht vorn). Im schlechtesten Fall (Worst Case) $n$ Vergleiche, wenn der Wert ganz hinten steht oder fehlt. Der Aufwand wächst also proportional zu $n$.
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…
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.
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…
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.
Binäre Suche
Beim Telefonbuch der Stadt Essen blätterst du nicht von Seite 1 an. Du schlägst in der Mitte auf, siehst, ob dein Name davor oder dahinter steht, und machst auf der richtigen Hälfte weiter. Genau das ist die binäre Suche.
Sie funktioniert nur, wenn das Feld sortiert ist. Denn nur dann sagt der Vergleich mit der Mitte, in welcher Hälfte der Wert liegen muss: Ist $x$ kleiner als das mittlere Element, stehen alle größeren Elemente rechts davon und kommen nicht mehr in Frage.
Was passiert, wenn der Wert fehlt? Suche 30 im Feld $[3, 9, 14, 21, 27, 33, 40]$: Irgendwann gilt links > rechts. Der Suchbereich ist leer, das Verfahren bricht ab und liefert −1.
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…
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…
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.
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).…
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).
- a) Führen Sie die binäre Suche nach 52 durch und protokollieren Sie jeden Schritt.
- b) Führen Sie die binäre Suche nach 30 durch und geben Sie an, wann und warum das Verfahren abbricht.
- c) Vergleichen Sie die Anzahl der Vergleiche mit der linearen Suche nach 52.
Binäre Suche in Java
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 (x < a[mitte]) {
rechts = mitte - 1;
} else {
links = mitte + 1;
}
}
return -1;
}
Zwei Stellen sind besonders wichtig:
-
Mitte:
(links + rechts) / 2ist eine ganzzahlige Division, sie rundet ab. -
Abbruchbedingung: Die Schleife läuft, solange
links <= rechts. Mit<würde ein Suchbereich aus genau einem Element nie geprüft.
Warum ist die Methode korrekt? Die Schleifeninvariante lautet: „Falls x im Feld vorkommt, steht es im Bereich von links bis rechts.“ Vor der Schleife stimmt das, denn der Bereich ist das ganze Feld. In jedem Durchlauf wird nur ein Teil verworfen, in dem x wegen der Sortierung nicht stehen kann, die Invariante bleibt also wahr. Außerdem wird der Bereich in jedem Durchlauf kleiner, die Schleife endet. Bei Abbruch ist der Bereich leer, also kommt x nicht vor.
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…
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.
Aufwand im Vergleich
Die binäre Suche halbiert den Suchbereich in jedem Schritt. Bei $n$ Elementen brauchst du im ungünstigsten Fall so viele Vergleiche, wie oft du $n$ halbieren kannst, bis nur noch ein Element bleibt. Das sind höchstens $\lfloor \log_2 n \rfloor + 1$ Vergleiche.
| Elemente $n$ | lineare Suche (Worst Case) | binäre Suche (Worst Case) |
|---|---|---|
| 8 | 8 | 4 |
| 1.000 | 1.000 | 10 |
| 1.000.000 | 1.000.000 | 20 |
Verdoppelst du $n$, kommt bei der binären Suche nur ein Vergleich hinzu, bei der linearen Suche verdoppelt sich der Aufwand.
Hat die binäre Suche also immer Vorteile? Nein. Sie braucht ein sortiertes Feld. Ist es unsortiert, musst du erst sortieren. Das kostet etwa $n \cdot \log_2 n$ Zugriffe, einmalig. Bei sehr wenigen Suchanfragen lohnt sich das nicht, bei vielen Anfragen schon.
Zurück zum Anfang: In der Leipziger Bücherei brauchst du bei der binären Suche höchstens 10 Vergleiche statt 1.000.
Eine Stadtbücherei in Leipzig hat 1.000 nach Nummern sortierte Bücher. a) Wie viele Vergleiche braucht die lineare Suche im ungünstigsten Fall? b) Wie viele Vergleiche…
Eine Stadtbücherei in Leipzig hat 1.000 nach Nummern sortierte Bücher.
- a) Wie viele Vergleiche braucht die lineare Suche im ungünstigsten Fall?
- 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?)
- c) Wie ändert sich die höchste Zahl an Vergleichen der binären Suche, wenn sich die Bücherzahl verdoppelt?
Eine Datenbank enthält $n = 1.000.000$ sortierte Einträge. Ein Zugriff dauert 0,002 ms. a) Berechnen Sie die höchste Zahl an Vergleichen und die Gesamtzeit für die…
Eine Datenbank enthält $n = 1.000.000$ sortierte Einträge. Ein Zugriff dauert 0,002 ms.
- 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.
- 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: a) Eine Liste mit 20 Namen, die sich ständig ändert. b) Ein sortiertes…
Beurteilen Sie, welches Suchverfahren Sie in folgenden Situationen wählen, und begründen Sie:
- a) Eine Liste mit 20 Namen, die sich ständig ändert.
- b) Ein sortiertes Archiv mit 50 Millionen Datensätzen, das selten geändert wird.
- c) Ein sortiertes Feld, in dem der gesuchte Wert mit hoher Wahrscheinlichkeit an den ersten Stellen steht.