Jump Search
Jump ahead by √n steps then do linear search within the block.
How it works
Jump Search is a block-based algorithm for sorted arrays that balances the simplicity of linear search with the efficiency of binary search. It divides the array into blocks of size ⌊√n⌋ and jumps forward by that step until the current element equals or exceeds the target, then performs a short backward linear scan within the identified block.
The optimal block size is ⌊√n⌋, which yields a worst-case O(√n) complexity — the same for both the jumping and linear phases. Unlike binary search, jump search moves in only one direction (forward), which makes it well-suited for media where backward seeks are expensive, such as magnetic disks or tape drives.
Phase 1 — Jumping: advance blockEnd by blockSize until arr[blockEnd] ≥ target or end of array is reached.
Phase 2 — Linear scan: search element-by-element from blockStart to min(blockEnd, n-1) for the exact target value.
Complexity
Visualizer
Where it's used in the real world
Ordered disk block search
Locating a record in a sequentially ordered file on diskDisk seek time is asymmetric — seeking backward is more expensive than seeking forward. Jump search's unidirectional nature minimises costly backward seeks while still outperforming a full linear scan by a factor of √n.
Database B-tree sequential scan fallback
Range scan within a leaf page after initial binary descentAfter a B-tree traversal lands on a leaf page, the engine may use a jump-style scan to quickly skip over large runs of non-matching records before switching to element-by-element inspection near the target range boundary.
Sensor data stream searching
Finding threshold crossings in a monotonically recorded sensor logIoT and telemetry systems often store timestamped sensor readings in append-only sorted buffers. Jump search quickly identifies the block containing a threshold crossing and pins down the exact crossing point with a local scan.
Implementation
function jumpSearch(arr: number[], target: number): number {
const n = arr.length;
const blockSize = Math.floor(Math.sqrt(n));
let blockStart = 0;
let blockEnd = blockSize - 1;
// Phase 1: jump forward until overshoot or end of array
while (blockEnd < n && arr[Math.min(blockEnd, n - 1)] < target) {
blockStart = blockEnd + 1;
blockEnd += blockSize;
}
// Phase 2: linear scan within the identified block
const end = Math.min(blockEnd, n - 1);
for (let i = blockStart; i <= end; i++) {
if (arr[i] === target) return i;
if (arr[i] > target) break;
}
return -1; // not found
}
// Usage — array must be sorted
const sorted = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 23, 29, 31, 37];
console.log(jumpSearch(sorted, 23)); // 10
console.log(jumpSearch(sorted, 20)); // -1