Jump search sits between linear search (O(n)) and binary search (O(log n)) in both complexity and simplicity. It works by jumping forward through a sorted array in fixed steps of √n, then doing a small linear scan once it overshoots the target.
The key insight is that jumping in blocks is faster than checking every element, but simpler than the recursive halving of binary search. With step size √n the algorithm makes √n jumps and then up to √n linear comparisons — giving O(√n) total. For n=10,000 that is 100 comparisons, versus 10,000 linear or 14 binary.
Jump forward by √n until arr[jump] ≥ target. You've overshot. Go back to the previous jump position and scan linearly up to √n elements. Two phases, both O(√n).
With step size k, you make n/k jumps and then up to k linear comparisons. Total = n/k + k. Minimising this with calculus gives k = √n as the optimal step, yielding O(√n).
Jump search uses sorted order to decide when to stop jumping — when arr[jump] ≥ target, we know the target must be in the previous block. Without sorting, you cannot make this inference.
Unlike binary search which can jump in both directions, jump search only moves forward during the jump phase. This makes it preferable in systems where backward seeking is expensive, like magnetic tape or network streams.
TIPWatch the two phases: the AMBER jump phase leaps by √n each step until overshooting the target. Then the PURPLE linear scan checks each element in the block individually. The jump phase is fast but imprecise — the linear scan is slow but exact. Together they balance at O(√n).
COLOUR LEGEND
Overshot — switch to linear