SearchingSearching

Jump Search

Search a sorted array by jumping ahead in fixed blocks of size √n, then scanning linearly within the block.

Learn Jump Search →
2
0
↑prev
5
1
8
2
12
3
↑step
16
4
23
5
38
6
56
7
72
8
91
9
1/6n=10, so the block size is floor(sqrt(n)) = 3. Jump ahead in blocks until a block end exceeds the target, then scan that one block linearly.
Block end / element comparedBlock to scan linearlyTarget foundEliminated
PseudocodeLearn Jump Search →
1step = floor(sqrt(n)); prev = 0
2while a[min(step, n) - 1] < target:
3  prev = step; step += floor(sqrt(n))
4  if prev >= n: return -1
5for i in prev .. min(step, n) - 1:
6  if a[i] == target: return i
7return -1
Variables
n10
jump3
prev0
step3
target23
Complexity
best O(1)
avg O(√n)
worst O(√n)
space O(1)
Speed