Exponentielle Suche
Die binäre Suche muss wissen, wo die Liste endet, bevor sie in der Mitte nachsehen kann. Die exponentielle Suche nicht: Sie galoppiert in immer größeren Schritten vorwärts, bis sie über den Zielwert hinausschießt, und durchsucht dann den letzten Schritt mit binärer Suche. Das macht sie ideal für Listen unbekannter Länge und schnell für Werte nahe am Anfang.
Die Idee
Prüfen Sie den Wert an Platz 1, dann 2, 4, 8, 16 und so weiter, jeder Platz doppelt so weit wie der vorige. Solange der Wert dort kleiner als der Zielwert ist, muss der Zielwert weiter hinten liegen. Sobald ein Wert zum ersten Mal nicht kleiner ist, sitzt der Zielwert in der Falle: Er liegt nach dem zuvor geprüften Platz und nicht später als dieser. Dieser Abschnitt ist sortiert, also findet eine binäre Suche den Zielwert oder zeigt, dass er fehlt.
Ein Beispiel
Suchen Sie in 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 nach 23. Platz 1 enthält 2, Platz 2 enthält 5, Platz 4 enthält 12, alle kleiner. Platz 8 enthält 56, das ist größer, also kann 23 nur an den Plätzen 5 bis 7 stehen. Die binäre Suche prüft deren Mitte, Platz 6, und findet 23: 5 Vergleiche, wo die einfache binäre Suche 3 braucht. Die Suche nach 12 in derselben Liste endet nach 3 Vergleichen an Platz 4, einer weniger als bei der binären Suche, und 2 wird an Platz 1 mit einem einzigen Vergleich gefunden.
Wie viele Vergleiche
Für einen Zielwert an Platz i endet das Verdoppeln nach etwa log₂ i Schritten und lässt einen Abschnitt von weniger als i Plätzen übrig, den die binäre Suche in etwa log₂ i weiteren abdeckt. Die Suche kostet also etwa 2 log₂ i Vergleiche, egal wie lang die Liste ist. Steht der Zielwert nahe am Anfang, schlägt das die binäre Suche, die immer etwa log₂ n braucht. Steht er nahe am Ende, braucht die exponentielle Suche bis zu etwa doppelt so viel. Bei 40 Werten braucht die App im Schnitt etwa 3 Vergleiche für die ersten fünf Plätze und etwa 9 für die letzten fünf, gegenüber etwa 4,6 bei der binären Suche.
Unbekannte Länge und Galoppieren
Jon Bentley und Andrew Yao beschrieben diese Verdopplungsstrategie 1976 für die unbeschränkte Suche: einen Wert in einer sortierten Folge ohne bekanntes Ende finden, etwa in einer unendlichen Liste oder einem Datenstrom, den man nur abtasten kann. Dieselbe Idee beschleunigt das Zusammenführen. Gewinnt einer von zwei sortierten Läufen immer wieder, wechselt Timsort in den Galopp-Modus: Es schaut im anderen Lauf 1, 2, 4, 8 Plätze voraus, um zu finden, wohin der nächste Wert gehört, statt Platz für Platz vorzugehen.
Selbst ausprobieren
Öffnen Sie die App, wählen Sie unter „Suchen nach“ einen Wert und drücken Sie „Schritt“. Jede Prüfung von Platz 1, 2, 4, 8 und so weiter wird hervorgehoben; sobald ein Wert nicht kleiner ist, wird der Abschnitt zwischen den letzten beiden Plätzen schattiert, und die binäre Suche übernimmt. Suchen Sie nach einem kleinen und dann nach einem großen Wert, und vergleichen Sie die Zahl mit der Kachel der binären Suche.
Häufig gestellte Fragen
Welche Zeitkomplexität hat die exponentielle Suche?
O(log i) für einen Zielwert an Platz i, also höchstens O(log n) für eine Liste mit n Werten. Sie braucht O(1) zusätzlichen Speicher und eine sortierte Liste.
Was ist der Unterschied zwischen exponentieller und binärer Suche?
Die binäre Suche beginnt mit der ganzen Liste und braucht deren Länge. Die exponentielle Suche findet zuerst durch Verdoppeln einen Abschnitt, der den Zielwert enthält, und durchsucht dann nur diesen Abschnitt mit binärer Suche. Sie ist schneller, wenn der Zielwert nahe am Anfang steht, und funktioniert, ohne die Länge zu kennen.
Warum den Schritt verdoppeln und nicht einen festen Betrag addieren?
Einen festen Schritt zu addieren ist die Sprungsuche, die etwa n geteilt durch die Schrittweite Prüfungen braucht, um die Liste zu durchqueren. Verdoppeln erreicht Platz i in etwa log₂ i Prüfungen, und der verbleibende Abschnitt ist nie mehr als doppelt so groß wie nötig, sodass die anschließende binäre Suche kurz bleibt.
Wo wird die exponentielle Suche verwendet?
Beim Durchsuchen unbegrenzter oder sehr langer sortierter Daten, beim Zusammenführen sortierter Läufe (Galoppieren in Timsort) und bei der Suche nach dem ersten Platz, an dem eine Bedingung wahr wird, wenn keine Obergrenze bekannt ist.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Exponentielle Suche ausprobieren