A searching algorithm for sorted arrays. The basic idea is to check fewer elements than linear search by jumping ahead by fixed steps and then doing a linear search in the identified block.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
{
"arr": "[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]",
"target": 55,
"n": 16
}Overview
Jump Search is a middle ground between linear and binary search for sorted arrays. Instead of checking every element, it jumps ahead in blocks of size √n until it passes the target, then does a short linear scan backwards inside the last block.
With a block size of √n there are at most √n jumps and at most √n steps in the final scan, so the total is O(√n). It is slower than binary search in theory, but it only ever moves forward through the data, which can matter when stepping backwards is expensive.
The default array is the first 16 Fibonacci numbers and the target is 55, so the block size is 4. The search checks the ends of blocks at indices 3 (value 2), 7 (13) and 11 (89). Since 89 is past the target, it scans forward from index 8 and finds 55 at index 10.
Step by step
- Set
step = floor(√n)andprev = 0. - While the last element of the current block,
arr[min(step, n) - 1], is less than the target, setprev = stepand advancestepby√n. Ifprev >= n, return -1. - Scan linearly from
prevwhilearr[prev] < target, stopping at the end of the block. - If
arr[prev]equals the target, returnprev; otherwise return -1.
Complexity
| Case | Cost | Why |
|---|---|---|
| Best case | O(1) | The target is in the first block, near its start. |
| Average case | O(√n) | About √n/2 jumps plus √n/2 scan steps. |
| Worst case | O(√n) | √n jumps plus a full √n-element scan. |
| Extra space | O(1) | Two indices. |
When to use it
- Sorted data on media where jumping back is costly, such as tape or some sequential storage.
- When you want something faster than linear search but simpler than binary search.
- As a building block for block-based indexes, where each block is scanned linearly.
Common mistakes
- The block size must be
√nfor the O(√n) bound; a fixed small step makes it linear. - Forgetting
min(step, n)reads past the end of the array on the final jump. - Like binary search, it requires sorted input.
A dry run is the best way to check your understanding of Jump Search: follow each row, predict the next one, and compare. The run below takes 21 steps in total. Steps that only re-print loop counters are left out so the decisions stand out. The Line column refers to the line numbers in the code listing above.
- Input
- 0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610
- Target
- 55
- Result
- return value = 10
| Step | Line | Array | What happens |
|---|---|---|---|
| 1 | 1 | [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610] | target = 55, n = 16 |
| 4 | 4 | [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610] | condition = 2 < 55 |
| 7 | 7 | [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610] | prev = 4, n = 16, condition = 4 >= 16 |
| 8 | 4 | [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610] | condition = 13 < 55 |
| 11 | 7 | [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610] | prev = 8, n = 16, condition = 8 >= 16 |
| 12 | 4 | [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610] | condition = 89 < 55 |
| 13 | 11 | [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610] | prev = 8, condition = 21 < 55 |
| 15 | 13 | [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610] | prev = 9, step = 12, n = 16, condition = 9 == 12 |
| 16 | 11 | [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610] | prev = 9, condition = 34 < 55 |
| 18 | 13 | [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610] | prev = 10, step = 12, n = 16, condition = 10 == 12 |
| 19 | 11 | [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610] | prev = 10, condition = 55 < 55 |
| 20 | 17 | [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610] | prev = 10, condition = 55 === 55 |
| 21 | 18 | [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610] | return value = 10 |