Jump Search

#How does it work?

Jump search walks a sorted array not one element at a time but in blocks of size √n. It checks the last element of each block; if the target is larger, the whole block is skipped.

Once the block that must hold the target is found, only that block is scanned from the start. That needs far fewer comparisons than linear search, and unlike binary search it never moves backwards and forwards.

That makes jump search attractive when going backwards is expensive, for example on tape or other sequential-access storage.

#Live animation

step = √n; prev = 0
while a[min(step, n) - 1] < target:
  prev = step; step = step + √n   (prev ≥ n → not found)
for i = prev to min(step, n) - 1:
  if a[i] == target: return i
return -1

#Step by step

1. 01Set the block size to √n.
2. 02Compare the last element of each block with the target.
3. 03If it is smaller than the target, jump to the next block.
4. 04If it is greater than or equal to the target, scan that block from the start.
5. 05If you run past the end or the block doesn't contain it, the value isn't there.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

import math


def jump_search(a: list[int], target: int) -> int:
    """a must be sorted. Jumps ahead in blocks of sqrt(n), then scans one block."""
    n = len(a)
    jump = int(math.sqrt(n))
    prev, step = 0, jump
    # Skip whole blocks whose last element is still smaller than the target.
    while a[min(step, n) - 1] < target:
        prev = step
        step += jump
        if prev >= n:
            return -1
    for i in range(prev, min(step, n)):
        if a[i] == target:
            return i
    return -1


numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(jump_search(numbers, 13))
print(jump_search(numbers, 4))

#Complexity

About √n jumps plus a scan of at most √n elements: O(√n) in total. Better than linear search's O(n), worse than binary search's O(log n). The block size is √n because jumps (n / m) plus the block scan (m) is smallest when m = √n.

#When to use it?

Useful when data is sorted but stepping backwards is expensive or impossible (sequential files, linked structures with skip pointers). The idea behind skip lists is similar. On random-access arrays binary search is usually faster.

#Practice

Log in to answer questions and save your progress.