SearchingAlgorithmaka block search

Jump Search

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

▶ VisualizePattern: Binary Search
Progress

Overview

Jump search works on a sorted array by stepping forward in blocks of size m (optimally m = √n) until it finds a block whose last element is ≥ the target, then scanning that block linearly. It costs O(√n) comparisons — between Linear Search and Binary Search.

Its selling point is that it only ever moves forward, so it suits media where jumping backwards is expensive (tape, sequential storage, singly linked lists with a skip index) and it makes fewer far jumps than binary search.

sortedO(√n)blocksequential access

Intuition

A mental model before the formal terms.

Looking for page 347 in a book with no index: flip ahead 20 pages at a time until you pass 347, then step back and turn single pages. With 400 pages you flip at most 20 big jumps plus 20 single pages, not 400.

How it works

  1. Choose the block size m = ⌊√n⌋.
  2. Set prev = 0, step = m. While a[min(step, n) - 1] < target: prev = step, step += m. If prev >= n, the target is absent.
  3. Linear-scan from prev while a[prev] < target; stop when reaching min(step, n).
  4. If a[prev] == target, return prev; otherwise return -1.

Why it works

Because the array is sorted, the target can only lie in the first block whose last element is ≥ the target — every earlier block ends below it.

At most n/m jumps plus at most m - 1 linear steps; minimizing n/m + m gives m = √n and a total of 2√n comparisons.

Recognition

How to tell a problem wants this.

  • Sorted data on a medium where backward seeks are costly or forbidden.
  • The problem asks for something better than linear but you cannot use random access freely (e.g. an indexed sequential file).
  • Rarely the intended answer in interviews — it appears mostly as a discussion of the √n decomposition idea.
“sorted array” → Binary Search

Interactive visualization

Play, step, change the input. ← → and space work too.

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

Pseudocode

1m = floor(sqrt(n)); prev = 0; step = m
2while a[min(step, n) - 1] < target:
3  prev = step; step += m
4  if prev >= n: return -1
5while a[prev] < target:
6  prev += 1
7  if prev == min(step, n): return -1
8if a[prev] == target: return prev
9return -1

Implementations

1import math
2from typing import Sequence
3 
4 
51 · Step forward in blocks of sqrt(n) until the block could contain target
6def jump_search(a: Sequence[int], target: int) -> int:
7    n = len(a)
8    if n == 0:
9        return -1
10    step = max(1, math.isqrt(n))
11 
12    prev, curr = 0, step
13    while prev < n and a[min(curr, n) - 1] < target:
14        prev = curr
15        curr += step
16        if prev >= n:
17            return -1  # ran off the end without reaching target
18 
192 · Scan the identified block linearly; it holds at most step elements
20    end = min(curr, n)
21    for i in range(prev, end):
22        if a[i] == target:
23            return i
24        if a[i] > target:
25            break  # sorted, so no later element can match
26    return -1
27 
28 
293 · Why sqrt(n): n/step jumps plus step scans, minimised at step = sqrt(n)
30def worst_case_probes(n: int, step: int) -> int:
31    return n // step + step  # minimal at step = sqrt(n), giving 2*sqrt(n)
32 
33 
344 · On a random-access list binary search dominates; jump search is for
35# sequential sources where seeking backward is expensive or impossible
36def block_count_for(n: int) -> int:
37    return math.ceil(n / math.sqrt(n))
Walkthrough
  1. math.isqrt(n) is the exact integer square root — no float round-trip, no rounding error, available since Python 3.8.
  2. prev, curr = 0, step uses tuple assignment for the two cursors, matching how the loop advances them together.
  3. a[min(curr, n) - 1] clamps the block-end probe exactly as in the other languages.
  4. range(prev, end) is half-open, which lines up with end = min(curr, n) being one past the last index to scan.
  5. The break on a[i] > target exploits sortedness to cut the average block scan in half.
Complexity (this implementation)
time O(sqrt(n)) · space O(1)

bisect is O(log n) and runs in C, so on a real list it beats this by a wide margin — jump search is for sequential sources.

Language notes
  • math.isqrt returns the floor of the exact square root for arbitrarily large integers, unlike int(math.sqrt(n)) which loses precision past 2^53.
  • math.sqrt returns a float and raises ValueError on negatives; isqrt raises on negatives too but never rounds.
  • For a genuinely sequential source, itertools.islice expresses "skip step items" without materialising them.
  • bisect_left is the right tool for any in-memory sorted list; this algorithm earns its place only when random access is expensive.
Common mistakes in this language
  • Using int(math.sqrt(n)) on a huge n, where float rounding can produce a step one too large and skip the target block.
  • Writing range(prev, end + 1), which reads one element past the block and, on the last block, past the list.
  • Forgetting the if prev >= n: return -1 guard, so a target above the maximum loops until min(curr, n) - 1 stops moving.
Language differences that matter here
  • Integer square root: Python has exact math.isqrt; C++, JavaScript and TypeScript go through a double sqrt and floor it, which is exact only below 2^53.
  • Clamping: C++ std::min requires matching types and needs explicit casts, while Math.min and Python min accept anything and coerce or compare directly.
  • The practical verdict is the same everywhere — std::lower_bound, bisect_left, or a hand-written binary search beats this on any random-access container.
  • Where it does win differs by ecosystem: paged network fetches in JS/TS, std::forward_list or memory-mapped tape in C++, and generator pipelines with itertools.islice in Python.

Complexity

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

At most 2√n comparisons with block size √n.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Sorted data where jumping backwards is expensive — sequential-access storage, tapes, one-directional cursors.
  • When the number of far jumps matters more than total comparisons (each jump is a costly seek).
  • As an intermediate technique to introduce √n decomposition.
Avoid it when
  • Ordinary in-memory sorted arrays — Binary Search is O(log n) and just as simple.
  • Unsorted data; the block test relies on sortedness.
  • Unbounded or unknown-length inputs — use Exponential Search.

Alternatives

Binary SearchExponential SearchLinear Search

Common mistakes

  • Indexing a[step - 1] past the end on the last block — always clamp with min(step, n).
  • Using block size n/2 or a constant instead of √n, losing the O(√n) bound.
  • Not handling the empty array or a target larger than every element.

Interview patterns

  • Explain the n/m + m trade-off and derive m = √n — a warm-up for √n decomposition and Mo's algorithm.
  • Compare seek counts: jump search makes ≤ √n forward seeks, binary search makes log n seeks that alternate direction.
Interview questions on this
Mock interviews

Example problems

No linked problems yet.