- Zielwert
- Aktueller Block
- Verglichen
- Ausgeschlossen
- Gefunden
Sprungsuche
Die Sprungsuche liegt zwischen linearer und binärer Suche. Sie geht eine sortierte Liste in Sprüngen von m Plätzen durch und prüft nur den letzten Wert jedes Blocks, bis sie einen Block erreicht, dessen letzter Wert nicht kleiner als das Ziel ist. Dann durchsucht sie diesen Block vom Anfang an. Wählen Sie den Wert und die Sprungweite und sehen Sie, wie viele Vergleiche die Sprünge und das Durchsuchen brauchen. Drücken Sie „Abspielen“, um die Suche anzusehen, oder gehen Sie mit „Schritt“ und „Zurück“ einen Vergleich nach dem anderen durch. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Die gestrichelte Linie markiert den gesuchten Wert, und der schattierte Bereich ist der aktuelle Block. Die Sprungsuche braucht eine sortierte Liste, daher wird eine unsortierte Liste zuerst sortiert. Wählen Sie den Wert, die Sprungweite 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, die Sprungweite und die Anzahl der Balken. Oder geben Sie eigene Zahlen ein: Die Sprungsuche sortiert sie zuerst.
- Drücken Sie „Abspielen“ oder gehen Sie mit „Schritt“ und „Zurück“ einen Vergleich nach dem anderen durch. Ziehen Sie den Schrittregler, um an eine beliebige Stelle der Suche zu springen.
- Probieren Sie bei 40 Balken die Sprungweiten 2 und 8 aus und vergleichen Sie die Zahl der Vergleiche mit der bei √n.
So funktioniert die Sprungsuche
Teilen Sie die sortierte Liste in Blöcke aus m Werten. Sehen Sie sich den letzten Wert des ersten Blocks an. Ist er kleiner als das Ziel, kann das Ziel nirgends in diesem Block sein; springen Sie also zum Ende des nächsten Blocks und sehen Sie wieder nach. Sobald der letzte Wert eines Blocks nicht kleiner ist, kann das Ziel nur in diesem Block sein: Gehen Sie zu seinem Anfang zurück und prüfen Sie seine Werte einzeln, bis Sie das Ziel finden oder daran vorbei sind.
Die Sprungweite wählen
Bei n Werten brauchen die Sprünge bis zu n/m Vergleiche und das Durchsuchen bis zu m. Kleine Sprünge machen das Durchsuchen kurz, aber die Sprünge zahlreich; große Sprünge bewirken das Gegenteil. Die Summe n/m + m ist am kleinsten bei m = √n, was etwa 2√n Vergleiche ergibt: höchstens 13 bei 40 Werten, gegenüber 40 bei der linearen und 6 bei der binären Suche. Die Sprungsuche geht nie mehr als einen Block zurück. Das hilft, wenn das Zurückgehen in den Daten langsam ist.
Häufig gestellte Fragen
Wie funktioniert die Sprungsuche?
In einer sortierten Liste springt sie in Schritten von m Plätzen vorwärts und prüft den letzten Wert jedes Blocks. Ist dieser Wert nicht mehr kleiner als das Ziel, kann das Ziel nur in diesem Block sein, den sie dann vom Anfang an durchsucht.
Welche Sprungweite ist am besten?
√n, gerundet. Die Sprünge kosten bis zu n/m Vergleiche und das Durchsuchen bis zu m; die Summe ist am kleinsten, wenn beide gleich sind, also bei m = √n. Das ergibt im schlimmsten Fall etwa 2√n Vergleiche.
Ist die Sprungsuche schneller als die binäre Suche?
Nein, die binäre Suche braucht weniger Vergleiche: etwa log₂ n gegenüber etwa 2√n. Die Sprungsuche kann trotzdem gewinnen, wenn das Zurückgehen in den Daten teuer ist, denn sie geht nur ein einziges Mal zurück, an den Anfang eines Blocks.
Welchen Treffer findet sie, wenn sich Werte wiederholen?
Den ersten. Jeder übersprungene Block endet mit einem Wert, der kleiner als das Ziel ist, also kann kein früherer Block einen Treffer enthalten, und das Durchsuchen beginnt am Anfang des Blocks.
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