Jump search

O(√n)

Jump search works on a sorted array: it jumps ahead in blocks of about √n, checking the block boundaries, until it passes the target — then it scans that one block linearly. Fewer comparisons than linear search, simpler than binary, at O(√n).

Array
Edit the input and press Play

How it works

  1. Jump ahead block by block (≈√n) until a block's last value is ≥ the target.
  2. Step back to the start of that block.
  3. Scan that block linearly for the target.
  4. If the block is exhausted without a match, it isn't present.

Pseudocode

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