# Jump Search, Explained Step by Step

> Jump ahead √n at a time, then walk back through one block.

Searching algorithm. Interactive version, with a step-by-step visualizer of a real recorded run: https://www.tmread.me/algorithms/jump-search

## Complexity

| | Big-O | Why |
|---|---|---|
| Best time | O(1) | The key is the first value checked. |
| Average time | O(√n) | About √n jumps, then at most √n steps inside one block. |
| Worst time | O(√n) | Same bound: √n jumps plus one block. |
| Extra space | O(1) | A few indexes. |

## 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.

1. Pick a block size `s`. The best choice is about `√n`, the square root of the list length.
2. Look at the last value of the first block, `a[s - 1]`.
3. While that value is smaller than the key, jump: the next block starts right after it, and you check that block’s last value.
4. Once a block’s last value is at least the key (or you reach the end), the key can only be in that block.
5. 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.

## Code

### Python

```python
def jump_search(a, key):
    n, s = len(a), max(1, isqrt(n))
    e, p, hi = min(s, n) - 1, 0, n - 1
    while e < n - 1 and a[e] < key:
        p, e = e + 1, min(e + s, n - 1)
    hi = e
    for i in range(p, hi + 1):
        if a[i] == key: return i
        if a[i] > key: p = hi + 1; break
        p = i + 1
    return -1
```

### TypeScript

```ts
function jumpSearch(a: number[], key: number) {
  const n = a.length;
  const s = Math.max(1, Math.floor(Math.sqrt(n)));
  let [e, p, hi] = [Math.min(s, n) - 1, 0, n - 1];
  while (e < n - 1 && a[e] < key) {
    [p, e] = [e + 1, Math.min(e + s, n - 1)];
  }
  hi = e;
  for (let i = p; i <= hi; i++) {
    if (a[i] === key) return i;
    if (a[i] > key) {
      p = hi + 1;
      break;
    }
    p = i + 1;
  }
  return -1;
}
```

### Go

```go
func jumpSearch(a []int, key int) int {
    n := len(a)
    s := max(1, int(math.Sqrt(float64(n))))
    e, p, hi := min(s, n)-1, 0, n-1
    for e < n-1 && a[e] < key {
        p, e = e+1, min(e+s, n-1)
    }
    hi = e
    for i := p; i <= hi; i++ {
        if a[i] == key {
            return i
        }
        if a[i] > key {
            p = hi + 1
            break
        }
        p = i + 1
    }
    return -1
}
```

## 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.

## Related algorithms

- [Linear Search](https://www.tmread.me/algorithms/linear-search.md): Check every value, left to right, until you find the key.
- [Binary Search](https://www.tmread.me/algorithms/binary-search.md): Check the middle of a sorted array and throw away the half that can’t hold the key.
- [Exponential Search](https://www.tmread.me/algorithms/exponential-search.md): Double a bound until it passes the key, then binary search that range.

---

From The Missing README (computer science, made visible). Want to run your own code and watch every step? Join Cohort 0, the early-access group: https://www.tmread.me/#cohort