Sprungsuche

Die Sprungsuche funktioniert wie die Suche nach einer Seite in einem Buch ohne Inhaltsverzeichnis: Sie blättern stückweise vor, achten auf die Seitenzahlen und blättern, sobald Sie zu weit sind, durch das letzte Stück zurück. In einer sortierten Liste braucht sie weit weniger Vergleiche, als jeden Wert zu prüfen.

Eine sortierte Reihe von Balken, in Blöcke aufgeteilt, der letzte Balken jedes übersprungenen Blocks ausgeblendet und der Block, der das Ziel enthalten kann, schattiert
Eine sortierte Reihe von Balken, in Blöcke aufgeteilt, der letzte Balken jedes übersprungenen Blocks ausgeblendet und der Block, der das Ziel enthalten kann, schattiert

Die Idee

In einer sortierten Liste verrät der letzte Wert eines Blocks, ob das Ziel überhaupt in diesem Block sein kann: Ist er kleiner als das Ziel, ist auch jeder andere Wert im Block kleiner. Sie müssen also nicht hineinschauen. Prüfen Sie der Reihe nach den letzten Wert jedes Blocks und überspringen Sie ganze Blöcke, bis einer nicht kleiner als das Ziel ist. Dann kann das Ziel nur in diesem Block sein: Durchsuchen Sie ihn vom Anfang an.

Ein Beispiel

Gesucht wird 23 in 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, mit Blöcken aus 3 Werten. Der erste Block endet mit 8, das ist kleiner, also wird er übersprungen. Der zweite Block endet mit 23, das ist nicht kleiner, also kann 23 nur in 12, 16, 23 sein. Beim Durchsuchen kommen 12, 16 und dann 23: gefunden nach 5 Vergleichen, wo die lineare Suche 6 und die binäre Suche 3 braucht. Bei der Suche nach 40 führen die Blockenden 8, 23 und 72 zum Block 38, 56, 72; 38 ist kleiner und 56 schon größer, also ist 40 nicht da: wieder 5 Vergleiche.

Warum √n

Bei Blöcken aus m Werten braucht das Finden des richtigen Blocks höchstens etwa n/m Vergleiche und sein Durchsuchen höchstens m. Wenige, lange Sprünge machen das Durchsuchen lang; viele kurze Sprünge machen das Springen lang. Die Summe n/m + m ist am kleinsten, wenn beide Teile gleich sind, also bei m = √n, und beträgt dann etwa 2√n. Bei 40 Werten heißt das Blöcke aus 6 Werten und höchstens 13 Vergleiche; bei einer Million Werten Blöcke aus 1.000 Werten und etwa 2.000 Vergleiche.

Wo sie passt

Die binäre Suche braucht weniger Vergleiche, etwa log₂ n. Aber sie springt in der ganzen Liste hin und her, während die Sprungsuche nur vorwärts geht und einmal zurück, an den Anfang eines Blocks. Das machte sie attraktiv für Daten auf Band oder in verketteten Strukturen, in denen das Zurückgehen langsam ist. Ben Shneiderman beschrieb sie 1978 als „jump searching“. Dieselbe Idee, in √n Blöcke aufzuteilen, oft Quadratwurzelzerlegung genannt, taucht in vielen anderen Algorithmen auf.

Ben Shneiderman (links) mit Catherine Plaisant auf dem Webshop 2012. Shneiderman beschrieb die Sprungsuche 1978.
Ben Shneiderman (links) mit Catherine Plaisant auf dem Webshop 2012. Shneiderman beschrieb die Sprungsuche 1978.

Selbst ausprobieren

Öffnen Sie die App, wählen Sie unter „Suchen nach“ einen Wert und drücken Sie „Schritt“. Jeder Sprung hebt den letzten Wert eines Blocks hervor; übersprungene Blöcke verblassen, und der Block, der das Ziel enthalten kann, ist schattiert, während er durchsucht wird. Stellen Sie bei 40 Balken die „Sprungweite“ von √n auf 2 oder 8 und sehen Sie, wie sich das Verhältnis von Sprüngen und Durchsuchen verschiebt.

Häufig gestellte Fragen

Welche Zeitkomplexität hat die Sprungsuche?

O(√n) bei Blöcken aus √n Werten: höchstens etwa 2√n Vergleiche. Sie braucht O(1) zusätzlichen Speicher und eine sortierte Liste.

Was ist der Unterschied zwischen Sprungsuche und binärer Suche?

Die binäre Suche halbiert jedes Mal den verbleibenden Teil und braucht etwa log₂ n Vergleiche, springt aber hin und her. Die Sprungsuche springt in festen Schritten vorwärts und durchsucht einen Block, braucht etwa 2√n Vergleiche und geht nur einmal zurück.

Kann der letzte Block stattdessen mit binärer Suche durchsucht werden?

Ja. Mit der binären Suche sinkt der Aufwand im Block von m Vergleichen auf etwa log₂ m. Die Sprünge kosten weiterhin n/m, daher lohnen sich dann größere Blöcke.

Braucht die Sprungsuche eine sortierte Liste?

Ja. Einen Block zu überspringen ist nur sicher, weil ein kleinerer letzter Wert bedeutet, dass jeder Wert darin kleiner ist. Die App sortiert eine unsortierte Liste zuerst.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Sprungsuche ausprobieren