# Jump Search

# 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

```id="jmp-1"
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

```id="py-jmp"
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
```

```id="go-jmp"
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
}
```