12.3 Sprungsuche

Die Grundidee der Sprungsuche

Das folgende Bild soll das Prinzip der Sprungsuche verdeutlichen:

Das Prinzip der Sprungsuche
Idee und Prompt: Ulrich Helmich 2026, Bild generiert von Mistral Vibe.

Gesucht wird die Zahl 192. Ein intelligenter Suchalgorithmus würde natürlich ganz rechts mit der Suche beginnen. Die hier dargestellte Sprungsuche startet aber ganz links bei Index 0.

Da zahl[0] = 1 kleiner als die Suchzahl 192 ist, wird gesprungen. Die ideale Sprungweite entspricht ungefähr der Quadratwurzel aus der Anzahl der Arrayelemente – bei 50 Elementen also 7.

Das nächste Element, das verglichen wird, ist zahl[7] = 29. Auch diese Zahl ist kleiner als die Suchzahl, also wird weiter gesprungen: zu zahl[14] = 58, zahl[21] = 86, zahl[28] = 115, zahl[35] = 143 und zahl[42] = 172. Auch diese Zahl ist noch kleiner als die Suchzahl, also wird zu zahl[49] = 200 am Ende des Arrays gesprungen.

Da die 200 nun größer als die Suchzahl 192 ist, muss die 192 im letzten Block liegen. Es wird zur letzten Sprungmarke zurückgesprungen (zahl[42], gestrichelter grüner Pfeil).

Von dieser Position ausgehend wird der letzte Zahlenblock nun sequentiell durchsucht. Nach fünf Vergleichen wird die Zahl 192 dann gefunden.

Insgesamt braucht die Sprungsuche in unserem Beispiel acht Sprünge sowie fünf Vergleiche, insgesamt also 13 Vergleiche. Eine binäre Suche nach der 192 hätte maximal 6 Vergleiche benötigt.