Overview
Jump Search is a search algorithm for sorted arrays that advances in fixed-size blocks instead of one element at a time. It jumps ahead by a fixed step until it overshoots the target, then does a short linear scan back within the last block.
It strikes a middle ground between Linear Search and Binary Search: fewer comparisons than a full scan, but without the arbitrary jumps of binary search — useful when jumping backward is more expensive than jumping forward.
How Jump Search works
- Choose a fixed step size, typically the square root of the array length (√n).
- Jump forward step positions at a time while the block's last element is still below the target.
- Once a block's end value meets or exceeds the target, stop jumping.
- Perform a linear scan from the start of that block toward its end to locate the target.
- Return the index if found, or report absence once the scan passes the target's value.
When to use it
- Sorted arrays where jumping backward is costly, so bounded forward jumps are preferable.
- Systems where sequential (forward) access is much faster than random access.
- A teaching example of trading between the O(n) scan and the O(log n) binary search.
Complexity analysis
With a step size of √n, Jump Search does about √n jumps plus a final scan of up to √n elements, giving O(√n) time in the worst case. That sits between Linear Search's O(n) and Binary Search's O(log n). It needs a sorted array and uses O(1) extra space.
Frequently asked questions
Why is √n the optimal step size?
The total cost is roughly (n/step) jumps plus step comparisons in the final block. Minimising that sum over step yields step = √n, which balances the two phases.
Is Jump Search ever better than Binary Search?
Asymptotically Binary Search's O(log n) wins, but Jump Search only ever moves forward and then scans locally, which can be friendlier on media where backward or random seeks are expensive.