Home/Searching/Jump search
Search algorithmsCTRL K

Jump search

· blocks of √n, then a linear scan
/searching/jump-search
COMPARISONS
0
probes so far
BLOCK
5
⌊√n⌋ elements per jump
JUMPS
0
blocks skipped
TARGET
33
value we look for
RESULT
—
index once found
skippedprobecurrent blocktargetfound
n = 32 · target 33 · seed 7 · block 5 · 10 steps
step 0 / 9
Size32
jump_search.ts
1
function jumpSearch(array: number[], target: number) {
2
  const block = Math.floor(Math.sqrt(array.length));
3
  let previous = 0, next = block;
4
  while (array[Math.min(next, array.length) - 1] < target) {
5
    previous = next;
6
    next += block;
7
    if (previous >= array.length) return -1;
8
  }
9
  for (let index = previous; index < Math.min(next, array.length); index++) {
10
    if (array[index] === target) return index;
11
  }
12
  return -1;
13
}
CURRENT STEP
line 2

Look for 33. Block size is ⌊√32⌋ = 5: jump that far, check the last element of the block.

// how it works

Understanding Jump search

jump search · skip ahead by √n, step back inside one block
01

The idea

Jump search reads only the last element of each block of √n elements. While that element is smaller than the target the whole block can be skipped; the first block whose last element is not smaller must contain the target, if it is anywhere, and a linear scan of that block finds it.

Both phases cost at most √n comparisons, so the total is about 2√n. That is far worse than binary search's log n, but every comparison after a jump moves forward through memory, which matters on tape, on linked storage or when jumping back is expensive.

02

The four stages

1
blocksize ⌊√n⌋
2
probethe last element of the block
3
jumpsmaller than the target: skip the block
4
scanthe block that stopped the jumps, linearly
03

Complexity

best
O(1)the target ends the first block
average
O(√n)half the jumps, half a block
worst
O(√n)2√n comparisons
space
O(1)two indices
04

Versus its siblings

COMPARISONS AT N = 1 000 · TARGET PRESENT
linear
500
jump
63
binary
10
ternary
13
interpolation
4
average over random targets · sorted, uniform values
05

Pseudocode

JUMPSEARCH(array, target)
  block ← ⌊√n⌋; previous ← 0; next ← block
  while array[min(next, n) − 1] < target: previous ← next; next ← next + block
  for index ← previous to min(next, n) − 1: if array[index] = target: return index
  return −1
06

When to use

Storage where moving backwards is costly: tapes, forward-only iterators, singly linked sorted lists.
When the comparison is much more expensive than a memory access and √n probes are acceptable.
07

Pitfalls

Block size must be √n for the 2√n bound; a fixed block size is linear again.
The last block may be shorter; clamp the probe index to n − 1.
On an array in RAM binary search is simply better; jump search is for constrained media.
08

History

Jump search is folklore from the era of sequential storage; Ben Shneiderman analysed it in 1978 in a paper on searching sorted sequential files, where he showed the √n block is optimal for one level of jumping and √n^(2/3)-style blocks for two.

Back to Searching