Jump Search
Jumps ahead through a sorted array in fixed-size blocks, then scans the one block that can hold the target.
How it works
Jump search works on a sorted array in two phases.
- Jump. It splits the array into blocks of √n values and checks the last value of each block, jumping one block at a time. As soon as that value is not smaller than the target, the target can only be in that block, because every earlier block ended with a smaller value.
- Walk. It scans that one block from its start, value by value, until it finds the target. If it reaches a larger value, or the end of the block, the target isn't there and it returns -1.
With 16 values, it jumps in blocks of 4: at most 4 jumps and then at most 4 steps inside a block, instead of up to 16 checks for linear search.
When to use it
Jump search is useful when jumping backwards is expensive, for example on data read from tape or a slow sequential stream: it moves forward in big jumps and only ever goes back once, by at most one block. Binary search needs fewer checks, so when you can jump anywhere in the array cheaply, use that instead.
Complexity
The block size √n is the sweet spot: bigger blocks mean fewer jumps but a longer walk, and smaller blocks the reverse. At √n both phases take at most √n steps.
| Case | Time | When |
|---|---|---|
| Best | O(1) | The target is the last value of the first block |
| Average | O(√n) | About √n / 2 jumps plus a walk through part of a block |
| Worst | O(√n) | It jumps to the last block and walks all of it |
| Extra space | Why |
|---|---|
| O(1) | It only keeps the block size and the block boundaries |
Implementations
function jumpSearch(array, target) {
const n = array.length;
if (n === 0) return -1;
const step = Math.floor(Math.sqrt(n));
let start = 0;
let end = step;
while (array[Math.min(end, n) - 1] < target) {
start = end;
end += step;
if (start >= n) return -1;
}
for (let i = start; i < Math.min(end, n); i++) {
const value = array[i];
if (value === target) return i;
if (value > target) break;
}
return -1;
}
import math
def jump_search(array, target):
n = len(array)
if n == 0:
return -1
step = math.isqrt(n)
start, end = 0, step
while array[min(end, n) - 1] < target:
start = end
end += step
if start >= n:
return -1
for i in range(start, min(end, n)):
if array[i] == target:
return i
if array[i] > target:
break
return -1
#include <algorithm>
#include <cmath>
#include <vector>
int jumpSearch(const std::vector<int>& a, int target) {
const int n = static_cast<int>(a.size());
if (n == 0) return -1;
const int step = static_cast<int>(std::sqrt(n));
int start = 0;
int end = step;
while (a[std::min(end, n) - 1] < target) {
start = end;
end += step;
if (start >= n) return -1;
}
for (int i = start; i < std::min(end, n); i++) {
if (a[i] == target) return i;
if (a[i] > target) break;
}
return -1;
}