Jump search

O(√n)

Jump search pracuje na seřazeném poli: skáče vpřed po blocích zhruba √n a kontroluje hranice bloků, dokud nepřekročí hledanou hodnotu — pak ten jeden blok projde lineárně. Méně porovnání než lineární, jednodušší než binární, O(√n).

Pole
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Skákej vpřed po blocích (≈√n), dokud poslední hodnota bloku není ≥ hledaná.
  2. Vrať se na začátek toho bloku.
  3. Projdi blok lineárně a hledej hodnotu.
  4. Když je blok vyčerpán bez shody, hodnota tam není.

Pseudokód

1jumpSearch(a, target):              # O(√n) — a is sorted2  step ← floor(√n); prev ← 03  while a[min(step,n)-1] < target:4    prev ← step; step ← step + floor(√n)5    if prev ≥ n: return -16  while a[prev] < target:            # linear scan in the block7    prev ← prev + 18    if prev = min(step,n): return -19  return (a[prev] = target) ? prev : -1