algorithms · searching · O(√n)

Jump Search

Binary search and exponential search both need to jump straight to an arbitrary index — arr[mid], arr[bound] — which is free on an array but not on every sorted structure: a sorted linked list, or any source that only exposes "read the next item," can't do it without walking there one node at a time. Jump search never asks for that. It fixes a block size, checks the last element of each block in turn — index m−1, 2m−1, 3m−1, … — until it finds a block whose last element is at least the target, then walks forward one element at a time through just that block. Every step, in both phases, moves strictly forward. The price for giving up random access is more total comparisons than binary search's O(log n) — the try-it demo below counts them for real, side by side with what binary search would need on the identical array and target, and with what every other block size would have needed too.

Try it

The array below has 36 elements, values 0, 4, 8, …, 140, chosen so its exact square root — the textbook "optimal" block size — is a clean 6. Pick a preset or edit the target and block size directly, then step through. The table under the stats recomputes, for the array and target currently loaded, how many comparisons every block size from 1 to 36 would have taken — real counts from the same code the visualizer runs, not a separate estimate.

preset

array target block size

Press Load, then Step through the search.

Why it works

Every jump-phase check keeps the same one-sided invariant exponential search's doubling phase uses, just walked in fixed strides instead of doubling ones: as long as arr[blockEnd] < target, the target — if present — can't be in that block or any earlier one, so it's safe to skip the whole block in a single comparison. The first block where that check fails (arr[blockEnd] ≥ target, or the array runs out) is guaranteed to either contain the target or prove it absent, because the previous block's last element was confirmed smaller. That's what makes the walk-forward scan inside the winning block always conclusive — it never needs to backtrack into an earlier block or peek into a later one:

step = blockSize
prev = 0
while prev < n and arr[min(step, n) - 1] < target:
    prev = step
    step += blockSize
# target (if present) is in [prev, min(step, n) - 1]
for i in prev .. min(step, n) - 1:
    if arr[i] == target: return i
    if arr[i] > target: break   # sorted array, can't appear later
return -1

Total comparisons are the jump-phase count plus the scan-phase count. Worst case, the jump phase checks every block boundary before the array runs out — up to ⌈n / m⌉ comparisons for block size m — and the scan phase then walks the entire winning block, up to m more. That's n/m + m total, and calculus (or just AM-GM) says a sum of the form x + n/x is minimized when x = √n, giving roughly 2√n comparisons at the optimum — which is where the "block size = √n" rule everyone quotes actually comes from. What that derivation glosses over: it's a bound on the worst case, not a promise about any one specific target. The table below sweeps every block size against every possible target on this page's 36-element array (every integer from −2 through 142, covering every element and every gap between them) and records the worst comparison count each block size ever produced — a real, exhaustively checked sweep, not the calculus estimate:

block size (m)	1	2	3	4	5	6	7	8	9	10	12	18	36
worst-case comparisons	36	19	14	12	11	11	11	11	12	12	14	19	36

The minimum (11 comparisons) isn't a single sharp point at m = 6 — it's a flat plateau covering block sizes 5 through 8, with √36 = 6 comfortably inside it, and the cost rises sharply toward either extreme (36 comparisons at m = 1 or m = 36 — see Pitfalls for why those two opposite-looking extremes land on the exact same number). "Pick block size √n" is good, verified advice for the worst case across every possible target. It is not a promise that √n is the best block size for any one target you actually run — the live sweep table above, for whichever specific target is currently loaded, regularly puts the true minimum somewhere else in that 5–8 neighborhood instead.

Reference implementation

function jumpSearch(arr, target, blockSize) {
  const n = arr.length;
  const m = Math.max(1, Math.floor(blockSize) || 1);
  let step = m, prev = 0;
  while (prev < n && arr[Math.min(step, n) - 1] < target) {
    prev = step;
    step += m;
  }
  if (prev >= n) return -1;
  for (let i = prev; i < Math.min(step, n); i++) {
    if (arr[i] === target) return i;
    if (arr[i] > target) break;
  }
  return -1;
}

Pitfalls

Both extreme block sizes degenerate to a plain linear scan — checked on this page's own array, target 100 (index 25). Block size 1 costs 26 comparisons: 25 one-at-a-time jump checks to walk up to the block containing index 25, plus 1 to confirm it inside a size-1 "block." Block size 36 — the whole array as one block — costs the identical 26: the single jump check at index 35 immediately fails (140 ≥ 100), so the scan phase does all the work, walking from index 0 to 25 to find it. Same total, for the same underlying reason: at either extreme, one of the two phases does nothing and the other phase is left to scan the array practically unassisted. The middle ground — a block size that actually lets both phases share the work — is where the real savings live.

√n minimizes the worst case, not every specific search — checked against the same array, target 61 (absent, between indices 15 and 16). Block size 6 (√36) costs 7 comparisons for this target; block size 8 costs only 3. Both sit inside the worst-case-optimal 5–8 plateau derived above, so neither is a bad choice — but for this one target, the textbook answer isn't the actual best one. Reload the demo with this target and compare against the live sweep table to see it directly.

It only pays for itself when random access is genuinely unavailable or genuinely expensive. On a plain array, where arr[i] is O(1) for any i, binary search's O(log n) beats jump search's O(√n) at every array size worth worrying about — 6 comparisons versus 11 in the worst case on this page's own 36-element array, and the gap only widens as n grows. The entire case for jump search rests on the access pattern, not the comparison count: it never needs to jump backward or land on an arbitrary index, only "read forward" and "skip ahead by a fixed count," which a sorted linked list (or any strictly-forward-only data source) supports directly and binary search's bisection cannot.

Complexity

O(√n) comparisons worst case, with the constant minimized (verified above) by a block size in the neighborhood of √n — better than plain linear scanning's O(n), worse than binary search's or exponential search's O(log n). Reach for it specifically when the underlying structure only supports forward, fixed-stride access — a sorted linked list is the standard example — where binary search's random-access bisection either can't run at all or degrades to O(n) per probe just to reach an arbitrary node. See Choosing a Search Algorithm for how it stacks up against the site's other ten Searching entries.