Jump Search
Springt in √n-Schritten durch ein sortiertes Array und sucht im richtigen Block dann linear.
- Vergleiche 0
- Ergebnis noch offen
- Vergleich
- Tausch
- sortiert
Pseudocode
1 step = floor(sqrt(n))
2 prev = 0
3 while a[min(step, n) - 1] < target
4 prev = step; step += floor(sqrt(n))
5 if prev >= n: return -1
6 while a[prev] < target
7 prev++; if prev == min(step, n): return -1
8 if a[prev] == target: return prev
9 return -1
Schritt-Log
Funktionsweise, Laufzeit und Speicher
Jump Search ist ein Suchverfahren für sortierte Arrays mit Random-Access. Statt wie die lineare Suche jedes Element einzeln zu prüfen oder wie die binäre Suche jeden Schritt zu halbieren, springt Jump Search in festen Sprungweiten der Größe √n vorwärts. An jedem Sprungziel wird geprüft, ob das Element bereits größer oder gleich dem Zielwert ist. Sobald das der Fall ist, durchläuft eine lineare Rückwärtssuche den letzten Block (also die √n Elemente seit dem vorletzten Sprung). Damit ergibt sich eine Laufzeit von O(√n) im Average und Worst Case, was zwischen der linearen O(n) und der binären O(log n) liegt. Der Speicherbedarf bleibt konstant bei O(1). Voraussetzung ist ein sortiertes Array.
Komplexität
- Best Case
O(1) - Average Case
O(√n) - Worst Case
O(√n) - Zusatz-Speicher
O(1)
Wann verwenden?
Sinnvoll, wenn die binäre Suche unattraktiv ist, weil das Sprungverhalten teuer ist (etwa auf Bandspeicher mit hohen Seek-Kosten oder auf sortierten Datenstrukturen, deren Mitte schwer berechnet werden kann), das Array aber trotzdem sequenziell schnell zu durchwandern ist. In der Praxis selten anzutreffen, in Lehrkontexten und in einigen Embedded-Use-Cases als kompromisslos einfache O(√n)-Suche aber relevant.