- Zielwert
- Noch möglich
- Verglichen
- Ausgeschlossen
- Gefunden
Exponentielle Suche
Die exponentielle Suche findet einen Wert in einer sortierten Liste in zwei Phasen. Zuerst prüft sie die Plätze 1, 2, 4, 8, 16 und so weiter und verdoppelt dabei jedes Mal, bis der Wert dort nicht kleiner als der Zielwert ist. Dann durchsucht sie den Abschnitt zwischen den letzten beiden Plätzen mit binärer Suche. Wählen Sie den gesuchten Wert und sehen Sie, warum Zielwerte nahe am Anfang mit nur wenigen Vergleichen gefunden werden. Drücken Sie „Abspielen“, um die Suche anzusehen, oder gehen Sie mit „Schritt“ und „Zurück“ Schritt für Schritt vor. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Die gestrichelte Linie markiert den gesuchten Wert, und der schattierte Bereich zeigt, wo er noch sein kann. Die exponentielle Suche braucht eine sortierte Liste, daher wird eine unsortierte Liste zuerst sortiert. Wählen Sie den Wert und die Anzahl der Balken, oder geben Sie eigene Zahlen ein. Ist das Feld ausgewählt, gehen die Pfeiltasten schrittweise vor, die Leertaste startet und pausiert, und Pos1 und Ende springen zum Anfang und zum Ende.
Wie es funktioniert
- Wählen Sie den gesuchten Wert und die Anzahl der Balken. Oder geben Sie eigene Zahlen ein: Die exponentielle Suche sortiert sie zuerst.
- Drücken Sie „Abspielen“ oder gehen Sie mit „Schritt“ und „Zurück“ Schritt für Schritt vor. Ziehen Sie den Schrittregler, um an eine beliebige Stelle der Suche zu springen.
- Suchen Sie einen Wert nahe am Anfang und einen nahe am Ende, und vergleichen Sie die Zahl mit „Binäre Suche bräuchte“.
So funktioniert die exponentielle Suche
Prüfen Sie den Wert an Platz 1. Ist er kleiner als der Zielwert, prüfen Sie Platz 2, dann 4, 8, 16, und verdoppeln Sie dabei jedes Mal. Sobald ein Wert nicht kleiner ist, hören Sie auf: Der Zielwert kann nur nach dem zuvor geprüften Platz und vor diesem liegen. Durchsuchen Sie diesen Abschnitt mit binärer Suche. Läuft das Verdoppeln über das Ende der Liste hinaus, durchsuchen Sie den Bereich vom zuletzt geprüften Platz bis zum Ende mit binärer Suche.
Schnell am Anfang, ohne Länge
Um einen Zielwert an Platz i zu erreichen, braucht das Verdoppeln etwa log₂ i Prüfungen. Der gefundene Abschnitt enthält weniger als i Werte, also braucht die binäre Suche etwa log₂ i weitere. Das sind insgesamt etwa 2 log₂ i, und das hängt davon ab, wo der Zielwert steht, nicht davon, wie lang die Liste ist. Zielwerte nahe am Anfang werden schneller gefunden als mit einfacher binärer Suche; Zielwerte nahe am Ende kosten bis zu etwa doppelt so viel. Da die Suche die Länge der Liste nie braucht, funktioniert sie auch bei Listen, die zu lang zum Messen sind oder kein bekanntes Ende haben.
Häufig gestellte Fragen
Wie funktioniert die exponentielle Suche?
In einer sortierten Liste prüft sie die Plätze 1, 2, 4, 8 und so weiter, bis der Wert dort nicht kleiner als der Zielwert ist. Dann kann der Zielwert nur zwischen den letzten beiden geprüften Plätzen liegen, und eine binäre Suche in diesem Abschnitt findet ihn.
Ist die exponentielle Suche schneller als die binäre Suche?
Wenn der Zielwert nahe am Anfang der Liste steht, ja: Für einen Zielwert an Platz i braucht sie etwa 2 log₂ i Vergleiche, egal wie lang die Liste ist. Steht der Zielwert nahe am Ende, ist die einfache binäre Suche schneller, bis zu etwa doppelt so schnell.
Wofür wird sie verwendet?
Zum Durchsuchen von Listen mit unbekannter oder unbegrenzter Länge, etwa einem Datenstrom oder einer unendlichen Folge, und zum Zusammenführen sortierter Läufe, bei denen der nächste Treffer meist in der Nähe liegt. Der Galopp-Modus von Timsort nutzt dieselbe Idee des Verdoppelns.
Warum heißt sie exponentiell?
Weil die geprüften Plätze exponentiell wachsen: 1, 2, 4, 8, 16, jeder doppelt so groß wie der vorige. Sie heißt auch Verdopplungssuche oder Galopp-Suche.
Werden meine Zahlen irgendwohin gesendet?
Nein. Die Suche läuft in Ihrem Browser, und Ihre letzten Einstellungen bleiben im lokalen Speicher dieses Browsers.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Zum Editor