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
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
More options
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 |
Scroll the table sideways for the rest of the columns.
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) |
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
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 -1