What is jump search?
Jump search finds a key in a sorted list by jumping ahead in fixed-size blocks, then walking through one block step by step.
Imagine a dictionary with no letter tabs. You flip ahead 50 pages at a time until you pass the word you want, then go back and read the last 50 pages one by one. That is jump search.
It sits between linear search, which checks every value, and binary search, which halves the list each time. It needs sorted input, like binary search, but it only ever moves forward.
How it works, step by step
Press play above. lo and hi mark the part of the list that can still hold the key, and everything outside them fades out as it is ruled out. The blue bar is being compared with the key.
- Pick a block size
s. The best choice is about√n, the square root of the list length. - Look at the last value of the first block,
a[s - 1]. - While that value is smaller than the key, jump: the next block starts right after it, and you check that block’s last value.
- Once a block’s last value is at least the key (or you reach the end), the key can only be in that block.
- Scan the block from the start. Return the position if you find the key. If you pass a value bigger than the key, stop: it is not there.
In the code, the while loop is the jumping phase, and the for loop is the walk through one block. Try “absent” to see the early stop: the walk quits as soon as it passes a value bigger than the key.
Time and space complexity
With blocks of size s, there are at most n / s jumps, and then at most s steps inside one block. The total is n/s + s. That is smallest when s = √n, giving about 2√n checks.
Best case, O(1): the key is the first value checked. Average and worst case, O(√n).
How does that compare? For a million values: linear search can take a million checks, jump search about 2,000, and binary search about 20. So jump search is much faster than linear search and much slower than binary search.
Space is O(1). A few indexes.
Why not always use binary search?
On an array in memory, binary search wins. Jump search earns its place when going backward is expensive. It moves forward in jumps and steps back at most once, to the start of one block. Binary search jumps back and forth all over the data.
That can matter for data on tape, on a slow disk, or in a linked structure where skipping ahead is cheap but going back is not.
Common mistakes
- Jumping past the end. Clamp each jump with
min(e + s, n - 1). - Using a block size of 0 on tiny lists. Clamp it with
max(1, …). - Scanning the wrong block. When the jump stops, the key is in the block that ends at the current index, not the next one.
- Forgetting the early stop in the walk. On a sorted list, once you pass a value bigger than the key, you can say “not found”.
When to use it
Use it on sorted data where moving backward costs a lot, or when you want something simpler than binary search that is still far faster than a full scan.
For sorted arrays in memory, binary search is the better default. Jump search is still a great lesson in picking a parameter: the √n block size comes straight from balancing two costs.
Questions
- What is the best block size for jump search?
- About √n. It balances the number of jumps (
n/s) against the walk inside one block (s). - Does jump search need a sorted list?
- Yes. It skips whole blocks because every value in them is known to be smaller than the key.
- Is jump search faster than binary search?
- No. O(√n) is slower than O(log n). It wins only when going backward through the data is expensive.