Algorithms · Searching

Jump Search

The idea

Looking for house number 57 on a long street, you do not read every door. You walk a block, check the corner house, walk another block — and once a corner shows a number bigger than 57, you turn around and check that block door by door.

The problem

Between checking every item (linear) and clever halving (binary) there is a middle path: jump ahead in fixed-size blocks until you pass the target, then step back and walk the last block one by one. The sweet spot is a block of about √n items.

Why it's slow

Jump search costs about √n comparisons: jumping to the right block takes up to √n probes, and walking inside it up to √n more. For 10,000 items that is roughly 200 comparisons — far better than linear search's 10,000, but well behind binary search's 14. So why learn it? It shines when stepping backwards is expensive (like on tape or disk) — and it teaches the art of the trade-off.

Pseudocode

  1. works on a sorted list
    Explain this line

    Like binary search, jumping only makes sense on sorted data.

  2. jump ahead in blocks of about √n
    Explain this line

    For 9 items the block is 3; for 100 items it would be 10.

  3. compare the block edge with the target; too small? jump again
    Explain this line

    Each probe skips a whole block of items in one comparison.

  4. step back into the block and walk one by one
    Explain this line

    The target must be inside the block we just overshot.

  5. found it — stop
    Explain this line

    A short linear walk finishes the job.

Complexity

Best Average Worst Space
O(1) O(√n) O(√n) O(1)

A deliberate compromise: fewer probes than linear search, simpler movement than binary search. Real lesson: algorithm design is about trade-offs, not silver bullets.

Code

python 
import math

def jump_search(a, target):  # a must be sorted
    n = len(a)
    block = math.isqrt(n) or 1
    prev = 0
    while prev < n and a[min(prev + block, n) - 1] < target:
        prev += block
    for i in range(prev, min(prev + block, n)):
        if a[i] == target:
            return i
    return -1
java 
int jumpSearch(int[] a, int target) { // a must be sorted
    int n = a.length;
    int block = Math.max(1, (int) Math.sqrt(n));
    int prev = 0;
    while (prev < n && a[Math.min(prev + block, n) - 1] < target) {
        prev += block;
    }
    for (int i = prev; i < Math.min(prev + block, n); i++) {
        if (a[i] == target) return i;
    }
    return -1;
}
cpp 
int jumpSearch(const std::vector<int>& a, int target) {
    int n = static_cast<int>(a.size());
    int block = std::max(1, (int)std::sqrt(n));
    int prev = 0;
    while (prev < n && a[std::min(prev + block, n) - 1] < target) {
        prev += block;
    }
    for (int i = prev; i < std::min(prev + block, n); ++i) {
        if (a[i] == target) return i;
    }
    return -1;
}
javascript 
function jumpSearch(a, target) { // a must be sorted
  const n = a.length;
  const block = Math.max(1, Math.floor(Math.sqrt(n)));
  let prev = 0;
  while (prev < n && a[Math.min(prev + block, n) - 1] < target) {
    prev += block;
  }
  for (let i = prev; i < Math.min(prev + block, n); i++) {
    if (a[i] === target) return i;
  }
  return -1;
}
dart 
import 'dart:math';

int jumpSearch(List<int> a, int target) { // a must be sorted
  final n = a.length;
  final block = max(1, sqrt(n).floor());
  var prev = 0;
  while (prev < n && a[min(prev + block, n) - 1] < target) {
    prev += block;
  }
  for (var i = prev; i < min(prev + block, n); i++) {
    if (a[i] == target) return i;
  }
  return -1;
}

Quick check