1. One-Liner
Jump search moves ahead in steps of about √n on a sorted array, then scans linearly inside the bracketing block.
2. The Problem It Solves
You want a simple O(√n) search that uses fewer jumps than checking every element but no random heavy math like interpolation—useful when forward-only or block-oriented access is natural.
3. The Core Idea
Hop like a kangaroo: big jumps until you overshoot or pass the target’s zone, then walk the last short stretch. The optimal jump size √n balances jumps vs linear work.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | Set step k = ⌊√n⌋, prev = 0. |
| 2 | Jump: while arr[min(j,n)-1] < target, set prev = j, j += k. |
| 3 | Linear search from prev to min(j, n). |
| 4 | Return index or -1. |
5. Dry Run Example
Array: [1,3,5,7,9,11,13,15,17] (n=9, step=⌊√9⌋=3), target: 11.
| Step | prev | Check index min(prev+step,n)-1 | Value | Condition |
|---|---|---|---|---|
| Jump 1 | 0 | 2 | 5 | 5 < 11 → prev = 3 |
| Jump 2 | 3 | 5 | 11 | 11 < 11 is false → stop jumping |
Linear scan from prev=3: compare 7, 9 (still < 11), then index 5 with value 11 → found at index 5.
6. Key Properties
| Property | Detail |
|---|---|
| Time | O(√n) comparisons (optimal jump size). |
| Space | O(1) |
| Vs binary | Worse asymptotic time but simpler and friendly to block storage. |
7. Where It Is Used
| Company / domain | Use |
|---|---|
| Storage | Searching within disk blocks or SSTable segments. |
| Embedded | Predictable, low overhead vs complex tree walks. |
8. Interview Tips
Derive why √n: minimize n/k + k → k = √n. Mention sorted prerequisite and linear tail.
9. Comparison with Other Algorithms
| Algorithm | Complexity |
|---|---|
| Binary | O(log n) — faster asymptotically. |
| Jump | O(√n) — good for block-oriented access. |
| Linear | O(n) — no ordering used. |
10. Complexity
| Time | Space |
|---|---|
| O(√n) | O(1) |
Implementation Example (PYTHON)
import math
def jump_search(arr, target):
n = len(arr)
if n == 0:
return -1
step = int(math.sqrt(n))
prev = 0
while prev < n and arr[min(prev + step, n) - 1] < target:
prev += step
if prev >= n:
return -1
while prev < n and arr[prev] < target:
prev += 1
if prev < n and arr[prev] == target:
return prev
return -1