Jump Search
Leap through a sorted array in √n-sized strides, then walk back linearly inside the one block that can hold the target.
Hands on Interactive visualization
Implementation Code
export function jumpSearch(a: number[], target: number): number {
const n = a.length;
if (n === 0) return -1;
const stride = Math.max(1, Math.floor(Math.sqrt(n)));
let prev = 0;
let step = stride;
// Leap until the block end reaches or passes the target.
while (a[Math.min(step, n) - 1] < target) {
prev = step;
step += stride;
if (prev >= n) return -1; // jumped past the end
}
// Linear scan inside the single candidate block.
for (let i = prev; i < Math.min(step, n); i++) {
if (a[i] === target) return i;
}
return -1;
}Big-O Complexity
Block size √n minimizes the total cost n/m + m. Roughly √n jumps plus √n linear steps — more comparisons than binary search, but strictly forward-moving after at most one step back.
In production When to use
On storage where a seek costs far more than a sequential read — tape archives, spinning disks, remote block ranges — jump search bounds the expensive backward movement to a single step back, then reads forward sequentially.
When you can only iterate forward with an occasional saved checkpoint (cursor-based APIs, forward iterators over sorted data), √n checkpoints give a real speedup over a pure scan without needing random access.
Jump search is the one-level version of a skip list: express lanes that skip m elements at a time, then drop to the local lane. Redis sorted sets generalize exactly this idea to multiple levels.
A sparse index that stores every m-th key of a sorted file (as in LSM SSTable index blocks) is jump search materialized: jump through index entries, then scan the one data block.
The mostly-forward, mostly-sequential access pattern is friendlier to caches and prefetchers than binary search's random probes, which can matter for mid-sized arrays in tight loops.
Trade-offs Strengths & weaknesses
- O(√n) with only O(1) extra space and a dead-simple implementation.
- At most one backward step — ideal when going backward is expensive.
- Mostly sequential access: prefetcher- and cache-friendlier than binary search's random probes.
- Works with forward-only iteration plus checkpoints; no full random access required.
- The direct conceptual ancestor of skip lists and sparse indexes.
- Asymptotically worse than binary search: O(√n) vs O(log n) — 31623 vs ~30 steps at n = 10⁹.
- Still requires sorted input, the same maintenance burden as binary search.
- Optimal block size √n assumes uniform access costs; tuning it for real media takes measurement.
- Rarely the right default — it wins only when seek asymmetry or forward-only access applies.
- Insertions and deletions still cost O(n) in the underlying sorted array.
Intuition Mental model
Skipping stones, then walking back
You are searching for a house number on a long street. Instead of checking every house, you drive and stop only every tenth house — once you overshoot, you park and walk back through just one block.
- Drive forward checking every m-th house — each stop tells you whether you have passed the target yet.
- The first stop whose number is too big means the target lives in the block you just flew past.
- Back up one stop — a single backward move, the only one you will ever make.
- Walk that one block house by house: at most m doors to check.
- Choosing m = √n balances driving stops against walking: about √n of each.
Prep Interview questions
Why is √n the optimal jump size?
When would you prefer jump search over binary search on the same sorted data?
How does jump search relate to skip lists?
How do you handle the final block correctly when n is not a perfect square?
Could you jump with a different schedule than fixed √n strides?
Watch out Common bugs
Probing a[step - 1] without clamping to min(step, n) - 1 reads out of bounds once the stride passes the array end. The final partial block needs explicit clamping.
Scanning from prev without stopping at min(step, n) can walk past the block that was proven to contain the target, doing wasted work and masking logic errors.
floor(sqrt(n)) is 0 when n = 0 and 1 when n is small; a zero stride loops forever. Guard n == 0 and take max(1, floor(sqrt(n))) as the stride.
Like every sorted-array search, jump search silently returns wrong answers on unsorted data — the block test a[step-1] >= target is meaningless without order.
One screen Cheat sheet
Stride √n at a time until you overshoot, then linear-scan one block backward-bounded.
- Optimal stride is √n: minimizes n/m jumps + m scan steps.
- At most one backward step — the defining property vs binary search.
- Clamp every probe to min(step, n) - 1; the last partial block is bug territory.
- Requires sorted data, like all order-exploiting array searches.
- One-level skip list; multi-level generalization gives O(log n) with inserts.
- Wins on slow-seek media and forward-only cursors, loses to binary search otherwise.