Jump search
easySlower than binary search, but it seeks backwards at most once - which matters on tape, on a linked list, or on any paged structure where a backward jump is expensive.
O(1)Average O(√n)Worst O(√n)Space O(1)What to notice
√n is the optimal block size
With block size b you do n/b jumps then up to b linear steps. Minimising n/b + b gives b = √n and a total of 2√n. Any other block size is worse - the maths is visible in the two phases on screen.
Slower than binary search, but it steps back at most once
O(√n) loses to O(log n), but jump search seeks backwards at most once - a single step back to the start of the block it overshot. On a magnetic tape, a singly linked list, or a paged structure where backward seeks are expensive, that constraint is worth the extra steps.
Saved in this browser - no sign-up, nothing sent anywhere.
How jump search works
Read only the last element of each block. If it is still below the target, the whole block is too small - jump past it. The first block end that is not below the target traps the target inside that block, and a short linear scan finishes the job. Two phases: coarse jumps forward, then a fine scan.
The block size is a genuine optimisation problem: blocks of b cost about n/b jumps plus up to b scan steps. Minimising n/b + b gives b = √n and roughly 2√n comparisons in total - for 18 elements, blocks of 4 and about 8 probes. Any other block size does worse in the worst case.
Binary search beats it on comparisons - O(log n) against O(√n) - so the reason to reach for jump search is access pattern, not speed. It moves backwards at most once - one step back to the start of the block it overshot. On a magnetic tape, a singly linked list, or paged storage where a backward seek is expensive, almost-forward-only is worth the extra comparisons.
Step by step
- n = 18, so the block size is floor(√18) = 4. Search for 63 in the sorted array of 18 values.
- Probe the first block's end: a[3] = 17 < 63. The entire block a[0..3] is too small - jump past it.
- a[7] = 41 < 63: jump again. Two probes have now dismissed eight elements without reading them.
- a[11] = 63 is not below the target, so the jumping stops - 63 must be inside a[8..11] if it exists at all.
- Scan that block left to right: a[8] = 47, a[9] = 52, a[10] = 58 all miss, then a[11] = 63 - found at index 11.
- Seven comparisons in total, close to the 2√n bound of about 8 - a plain linear scan would have used 12.
Complexity
| Best case time | O(1) |
|---|---|
| Average time | O(√n) |
| Worst case time | O(√n) |
| Space | O(1) |
Minimising n/b + b over block size b gives b = √n.
Reference implementation
Python
import math
def jump_search(a, target):
n = len(a)
step = int(math.sqrt(n))
prev, cur = 0, step
while cur < n and a[cur - 1] < target:
prev, cur = cur, cur + step
if prev >= n:
return -1
for i in range(prev, min(cur, n)):
if a[i] == target:
return i
return -1JavaScript
function jumpSearch(a, target) {
const n = a.length, step = Math.floor(Math.sqrt(n));
let prev = 0, cur = step;
while (cur < n && a[cur - 1] < target) {
prev = cur; cur += step;
if (prev >= n) return -1;
}
for (let i = prev; i < Math.min(cur, n); i++) {
if (a[i] === target) return i;
}
return -1;
}Common pitfalls
- Forgetting min(cur, n) when the final block is partial - the block-end probe or the linear scan runs past the end of the array.
- Probing a[cur] instead of a[cur - 1]. The block end is the last index inside the block; off by one, and the block holding the target gets jumped over.
- A block size other than √n. The search still works, but the 2√n guarantee is gone - b = 1 and b = n both degenerate to linear search.
- Scanning from 0 instead of prev once the jumps stop - the answer is still right, but every jump was wasted work.
- Unsorted input: a block end below the target no longer proves the whole block is below it, so blocks are skipped wrongly. This module sorts your input first.
Where it is used
- Sequential media - tape drives and forward-only cursors, where binary search's backward jumps are prohibitively expensive.
- Singly linked lists of known length, where a forward hop is the only affordable move.
- Paged or block storage where every backward seek costs a fresh page load.
- The interview derivation: minimise n/b + b over the block size b - a small optimisation with a concrete payoff.
Frequently asked questions
What is the time and space complexity of jump search?
Average and worst case O(√n): about n/b jumps plus up to b scan steps, which the optimal block size b = √n turns into roughly 2√n comparisons. Best case O(1) when the first block-end probe is the target. Space is O(1).
Why is the optimal block size the square root of n?
The two phases trade off: bigger blocks mean fewer jumps but a longer final scan. The worst-case total n/b + b is minimised where the two terms are equal, at b = √n. For a million elements that means blocks of 1,000 and about 2,000 comparisons.
Is jump search better than binary search?
Not on comparison count - O(√n) loses to O(log n) badly as n grows. Jump search wins only when moving backwards is expensive: it steps back at most once, while binary search can reverse direction on every probe. Given cheap random access, use binary search.
Does jump search require a sorted array?
Yes. Skipping a whole block on the evidence of its last element only works if that element is the block's maximum, which sorted order guarantees. On unsorted data the target can hide inside a skipped block. This visualizer sorts whatever you type before searching.