How Jump Search Works
Jump search steps forward in fixed blocks until it overshoots, then scans the last block linearly. Slower than binary search, and the right shape when jumping backwards is expensive.
- Ruled out
- Still possible
- Checked now
- Found
Step 1 of 7
Looking for 158 in 16 sorted values, from 4 to 196.
Counters
- Steps
- 0
- Result
- -
- Still possible
- 16
- of 16
- Worst case
- 8
- steps for this size
Settings
Two to 64 numbers. Sorted ascending before the search runs.
Jump search
- 1
step = floor(sqrt(n)) - 2
// jump until the block may hold it - 3
while a[min(step, n) - 1] < target: - 4
prev = step; step += floor(sqrt(n)) - 5
- 6
// then walk the block - 7
for i in prev..min(step, n)-1: - 8
if a[i] == target: return i - 9
return NOT_FOUND
The same array, every algorithm
Probes on the values above, cheapest first. One probe is one value actually looked at.
- Interpolation1
- Ternary3
- Binary4
- Jump5
- Exponential8
- Linear13
How the six compare
| Algorithm | Best | Average | Worst | Needs a sorted array |
|---|---|---|---|---|
| Linear | O(1) | O(n) | O(n) | No |
| Binary | O(1) | O(log n) | O(log n) | Yes |
| Ternary | O(1) | O(log n) | O(log n) | Yes |
| Jump | O(1) | O(√n) | O(√n) | Yes |
| Exponential | O(1) | O(log n) | O(log n) | Yes |
| Interpolation | O(1) | O(log log n)* | O(n) | Yes |
Interpolation search only reaches that average when the gaps between the values are even.
Complexity
| Best | Average | Worst | Extra memory |
|---|---|---|---|
| O(1) | O(√n) | O(√n) | O(1) |
A block size of √n is optimal: it balances the number of jumps against the length of the final scan. For a million elements that is 1000 jumps rather than binary search's 20 comparisons.
How jump search works
Jump search moves forward in steps of √n, checking only the element at each landing point, until it finds one larger than the target. The target, if present, must lie in the block just passed, which it then scans element by element. Unlike binary search it only ever moves forward in large steps and backward in small ones, which matters on media where seeking is asymmetric.
- Choose a step size of √n.
- Jump forward step elements at a time while the landed-on value is still smaller than the target.
- Once a landed-on value exceeds the target, the answer lies in the block that was just skipped.
- Scan that block linearly from its start.
- Reaching the end of the block without a match means the value is absent.
Implementation
The same algorithm the visualiser is running, written to be read.
import math
def jump_search(values, target):
n = len(values)
step = max(1, int(math.isqrt(n)))
# Jump forward until the block containing the target is found.
previous, current = 0, 0
while current < n and values[current] < target:
previous = current
current += step
# Then walk that block.
for i in range(previous, min(current + 1, n)):
if values[i] == target:
return i
return -1When to use it
- Use it when moving backwards is costlier than moving forwards — tape, a sequential file, a cursor that only rewinds cheaply within a page.
- Use it where computing a midpoint repeatedly is awkward but striding is natural.
- Avoid it on an in-memory array. Binary search reaches the same element in log n steps rather than √n.
Check yourself
If the animation made sense, these should too.
Why is √n the optimal block size?
The cost is (n/step) jumps plus up to step steps in the final scan. That sum is smallest when the two terms are equal, which happens at step = √n, giving O(√n) overall.
Binary search is O(log n). When would you use O(√n) jump search instead?
When backward movement is much more expensive than forward movement - tape, a sequential file, a cursor that only rewinds cheaply within a page. Jump search only ever strides forward and then walks back a bounded amount.