Jump Search

Searching O(√n) O(1)

On a sorted array, leaps ahead in fixed blocks of √n to find the block that may hold the target, then scans that block linearly.

Idle

Sorted array of 8 — jump size = ⌊√8⌋ = 2.

InvariantEvery block end passed so far was smaller than the target, so the target cannot be in those blocks.

1/5

probes0step2prev0

checkingfoundeliminated

jump-search.c

int jumpSearch(int arr[], int n, int target) {
    int step = (int)sqrt(n);
    int prev = 0;
    while (arr[min(step, n) - 1] < target) {
        prev = step;
        step += (int)sqrt(n);
        if (prev >= n)
            return -1;
    }
    while (arr[prev] < target) {
        prev++;
        if (prev == min(step, n))
            return -1;
    }
    if (arr[prev] == target)
        return prev;
    return -1;
}

How Jump Search works

Leap through the sorted array in √n-sized blocks until you overshoot the target, then scan the previous block linearly.

Best case

Target sits at a block boundary: O(1) jumps.

Worst case

√n jumps plus √n scan steps: O(√n).

When to use it

Sorted data where jumping back is cheap but you want fewer comparisons than a full linear scan.