Jump Search

Jump search finds a target in a sorted array by skipping ahead in fixed-size steps and then performing a linear scan within a small block. It reduces the number of comparisons compared to linear search while avoiding full binary search.

Problem

Given a sorted array $A$ of length $n$ and a value $x$, find an index $i$ such that

$$ A[i] = x $$

If no such index exists, return $-1$.

Key Idea

Instead of checking every element, jump forward by a fixed step size $k$:

Check $A[0], A[k], A[2k], A[3k], \dots$
Stop when $A[j] \ge x$ or the end is reached
Perform linear search in the previous block

Optimal step size:

$$ k \approx \sqrt{n} $$

This balances the number of jumps and the size of the final scan.

Algorithm

jump_search(A, x):
    n = length(A)
    k = floor(sqrt(n))

    prev = 0
    curr = 0

    while curr < n and A[curr] < x:
        prev = curr
        curr = curr + k

    curr = min(curr, n - 1)

    for i from prev to curr:
        if A[i] == x:
            return i

    return -1

Example

Let

$$ A = [2, 4, 6, 8, 10, 12, 14, 16, 18] $$

and

$$ x = 12 $$

Step size:

$$ k = 3 $$

Jump phase:

step	index	value
1	0	2
2	3	8
3	6	14

Now the target lies in range $[3, 6]$. Linear scan finds index $5$.

Correctness

The jump phase finds a block such that:

$$ A[prev] < x \le A[curr] $$

Since the array is sorted, if $x$ exists, it must lie within this block. The linear scan checks all elements in that block.

Complexity

Let $k$ be the step size.

phase	cost
jumps	$O(n / k)$
linear scan	$O(k)$

Total:

$$ O\left(\frac{n}{k} + k\right) $$

Minimized when:

$$ k = \sqrt{n} $$

So:

$$ O(\sqrt{n}) $$

Space:

$$ O(1) $$

Comparison

method	requirement	time
linear search	none	$O(n)$
jump search	sorted	$O(\sqrt{n})$
binary search	sorted	$O(\log n)$

Jump search sits between linear and binary search.

When to Use

Sorted arrays with expensive random access
Situations where sequential access is cheaper
Systems where memory access patterns matter

Notes

Performs fewer comparisons than linear search
Simpler than binary search
Not optimal for very large datasets

Implementation

import math

def jump_search(a, x):
    n = len(a)
    k = int(math.sqrt(n))

    prev = 0
    curr = 0

    while curr < n and a[curr] < x:
        prev = curr
        curr += k

    curr = min(curr, n - 1)

    for i in range(prev, curr + 1):
        if a[i] == x:
            return i

    return -1

import "math"

func JumpSearch(a []int, x int) int {
    n := len(a)
    k := int(math.Sqrt(float64(n)))

    prev, curr := 0, 0

    for curr < n && a[curr] < x {
        prev = curr
        curr += k
    }

    if curr >= n {
        curr = n - 1
    }

    for i := prev; i <= curr; i++ {
        if a[i] == x {
            return i
        }
    }

    return -1
}