Jump Search

Jump search sits between linear and binary search on a sorted array. Instead of checking every element (linear) or halving the range (binary), it hops forward in fixed-size blocks until it overshoots the target, then walks backward through just the block it leapt over. The cleverness is all in the block size.

Two phases: leap, then scan back

1. 1Pick a block size m (the classic choice is √n).
2. 2Leap: check arr[m], arr[2m], arr[3m]… stepping forward by m each time.
3. 3Stop the moment a checked value is greater than the target (or you pass the end). The target, if present, is in the block just jumped over.
4. 4Scan back: walk that single block linearly, from the previous boundary forward, comparing each element.
5. 5Match → return the index; reach the block's end without one → the target isn't there.

Why the block size is √n

With a block size of m, the worst case does about n/m leaps to find the right block, then up to m back-steps to scan it: total work is roughly n/m + m. Calculus (or just trying values) shows this sum is smallest when `m = √n`, giving √n + √n = 2√n steps. Make blocks bigger and the back-scan grows; make them smaller and the leaps grow. √n is the sweet spot — hence O(√n).

function jumpSearch(arr, target) {
  const n = arr.length;
  const step = Math.floor(Math.sqrt(n));
  let prev = 0, curr = step;
  // leap until we overshoot or pass the end
  while (curr < n && arr[curr] < target) {
    prev = curr;
    curr += step;
  }
  // scan back through the one block [prev, min(curr, n))
  for (let i = prev; i < Math.min(curr, n); i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}