If binary search is O(log n), why might jump search read fewer values in a particular lookup? Try finding 2 and 46 in the same sorted array of 32 even numbers. Which algorithm wins changes with the target.
Which wins? Pick a target before you look at the probe counts.
▶ Watch the eight-second search race on YouTube · More visual explainers on the MyGearHut channel
Count reads on the same input
Here is what each search reads, in order, using a five-element jump block and a binary search that rounds its midpoint down.
| Target | Binary search reads | Jump search reads |
|---|---|---|
| 2 | 32 → 16 → 8 → 4 → 2 (5) | 10 → 2 (2) |
| 46 | 32 → 48 → 40 → 44 → 46 (5) | 10 → 20 → 30 → 40 → 50 → 42 → 44 → 46 (8) |
Jump search uses 10 to identify the first block for 2 and then reads the first element. For 46, it reads five block ends before scanning inside the fifth block. Both searches assume sorted input.
Reproduce the traces
The functions below return the values they inspected and whether the target was found. A probe is one array read. If jump search finds the answer at a block end, it exits immediately. If the end is above the target, it scans the earlier values in that block without reading the end twice.
const values = Array.from({ length: 32 }, (_, i) => 2 * (i + 1)); function binaryTrace(values, target) { const reads = []; let lo = 0; let hi = values.length - 1; while (lo <= hi) { const mid = lo + Math.floor((hi - lo) / 2); const value = values[mid]; reads.push(value); if (value === target) return { found: true, reads }; if (value < target) lo = mid + 1; else hi = mid - 1; } return { found: false, reads }; } function jumpTrace(values, target) { const reads = []; const blockSize = Math.max(1, Math.floor(Math.sqrt(values.length))); for (let start = 0; start < values.length; start += blockSize) { const end = Math.min(start + blockSize, values.length) - 1; const endValue = values[end]; reads.push(endValue); if (endValue === target) return { found: true, reads }; if (endValue < target) continue; for (let i = start; i < end; i++) { const value = values[i]; reads.push(value); if (value >= target) return { found: value === target, reads }; } break; } return { found: false, reads }; } for (const target of [2, 46, 45, 65]) { console.log(target, binaryTrace(values, target), jumpTrace(values, target)); } Try 45 next. Jump search stops scanning once it reaches 46. Because the array is sorted, every later value is at least 46, so 45 cannot appear later. Try 65 to see how the jump search handles the short final block.
Binary search has an O(log n) worst-case bound. With blocks of about √n elements, jump search checks at most about √n block ends and scans at most about √n elements, so its worst case is O(√n). Those bounds describe how work grows in the worst case. This experiment compares array reads for specific targets. It does not measure elapsed time.
Step through both searches in the browser. I built the demo for MyGearHut.
Algorithm references: binary search and jump search.
AI tools assisted with the draft and diagrams. The JavaScript examples were run to verify the reported traces.


