Jump Search
Jump Search skips ahead in blocks of size √n to find the target's block, then does a linear scan backward. It bridges the gap between O(n) linear and O(log n) binary search — achieving O(√n).
Search Target
↑ Set a target value above to begin searching the array
Legend
Inspector
Legend
Inspector
Reference implementation of Jump Search. Select a language tab to view and copy the code.
#include <math.h>
int jump_search(int arr[], int n, int target) {
int step = (int)sqrt((double)n);
int prev = 0;
/* Phase 1: jump by step until arr[end-of-block] >= target */
while (arr[MIN(step, n) - 1] < target) {
prev = step;
step += (int)sqrt((double)n);
if (prev >= n) return -1;
}
/* Phase 2: linear search within the block */
while (arr[prev] < target) {
prev++;
if (prev == MIN(step, n)) return -1;
}
return (arr[prev] == target) ? prev : -1;
}
/* MIN(a,b) = ((a)<(b)?(a):(b)) */#include <vector>
#include <cmath>
#include <algorithm>
int jumpSearch(const std::vector<int>& arr, int target) {
int n = static_cast<int>(arr.size());
int step = static_cast<int>(std::sqrt(n));
int prev = 0;
while (arr[std::min(step, n) - 1] < target) {
prev = step;
step += static_cast<int>(std::sqrt(n));
if (prev >= n) return -1;
}
while (arr[prev] < target) {
prev++;
if (prev == std::min(step, n)) return -1;
}
return (arr[prev] == target) ? prev : -1;
}public static int jumpSearch(int[] arr, int target) {
int n = arr.length;
int step = (int) Math.sqrt(n);
int prev = 0;
while (arr[Math.min(step, n) - 1] < target) {
prev = step;
step += (int) Math.sqrt(n);
if (prev >= n) return -1;
}
while (arr[prev] < target) {
prev++;
if (prev == Math.min(step, n)) return -1;
}
return (arr[prev] == target) ? prev : -1;
}import math
def jump_search(arr: list[int], target: int) -> int:
n = len(arr)
step = int(math.sqrt(n))
prev = 0
# Phase 1: jump over blocks
while arr[min(step, n) - 1] < target:
prev = step
step += int(math.sqrt(n))
if prev >= n:
return -1
# Phase 2: linear search within block
while arr[prev] < target:
prev += 1
if prev == min(step, n):
return -1
return prev if arr[prev] == target else -1function jumpSearch(arr, target) {
const n = arr.length;
const step = Math.floor(Math.sqrt(n));
let prev = 0, curr = step;
// Phase 1: jump over blocks
while (arr[Math.min(curr, n) - 1] < target) {
prev = curr;
curr += step;
if (prev >= n) return -1;
}
// Phase 2: linear search within block
while (arr[prev] < target) {
prev++;
if (prev === Math.min(curr, n)) return -1;
}
return arr[prev] === target ? prev : -1;
}Python — Code Walkthrough
import math for sqrt
import math; step = int(math.sqrt(n))math.sqrt returns a float; int() truncates it to ⌊√n⌋. Python does not overflow, but using int(math.sqrt(n)) is safer and clearer than n ** 0.5.
Phase 1 comment — blocks
# Phase 1: jump over blocksWhile the last element of the current block is less than target, the entire block can be skipped. min(step, n) prevents index out-of-range when n is not a perfect square.
Phase 2 comment — linear scan
# Phase 2: linear search within blockOnce the jump loop stops, we know target (if present) is between prev and min(step, n)−1. A simple forward walk checks each element.
Conditional return
return prev if arr[prev] == target else -1Python's conditional expression (ternary) reads naturally. After the linear scan arr[prev] is the first element ≥ target; we return prev only if it's an exact match.