Jump Search
Jumps through a sorted array in √n strides and scans the right block linearly.
- Comparisons 0
- Result still searching
- compare
- swap
- sorted
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
Step log
How it works, runtime and memory
Jump Search is a search method for sorted arrays with random access. Instead of probing every element like linear search or halving the range like binary search, Jump Search advances in fixed strides of size √n. At each jump position it checks whether the element is already ≥ target. As soon as that holds, a linear backward scan walks through the last block (the √n elements since the previous jump). This yields O(√n) runtime in average and worst case, between linear O(n) and binary O(log n). Memory stays constant at O(1). The array must be sorted.
Complexity
- Best case
O(1) - Average case
O(√n) - Worst case
O(√n) - Extra space
O(1)
When to use it
Useful when binary search is awkward because jumping is expensive (e.g. tape storage with high seek costs or sorted structures whose middle is hard to compute) but sequential traversal is cheap. Rare in practice, but relevant in teaching and in some embedded use cases as a compromise O(√n) search.