Jump Search works on sorted arrays by jumping ahead sqrt(n) positions at a time until an element greater than the target is found, then doing a linear search backward in the previous block. The optimal jump size is sqrt(n), giving O(sqrt(n)) time complexity — better than linear but worse than binary.
int jumpSearch(vector<int>& arr, int target) {
int n = arr.size(), step = sqrt(n), prev = 0;
while (arr[min(step,n)-1] < target) { prev = step; step += sqrt(n); if (prev >= n) return -1; }
while (arr[prev] < target) { prev++; if (prev == min(step,n)) return -1; }
return arr[prev] == target ? prev : -1;
}Jump Search divides the sorted array into blocks of size sqrt(n). It jumps between blocks until it finds a block that might contain the target, then linearly searches that block.
The optimal jump size minimizes total comparisons: n/m block jumps plus m linear steps. Setting n/m = m gives m = sqrt(n), for a total of 2*sqrt(n) comparisons in the worst case.
Jump Search is O(sqrt(n)) vs Binary Search O(log n). Binary Search is always faster asymptotically, but Jump Search only moves forward — useful for media files or tape storage where backward seeks are expensive.
Quiz coming soon for this algorithm.