Jump Search Algorithm — Block-Based Searching in O(√n)

Jump search is primarily of historical and theoretical interest today. In the era of magnetic tape and sequential storage devices, 'jumping forward' was cheap but 'seeking backward' was expensive — requiring physical rewinding. Jump search's forward-only movement was a genuine practical advantage.

For in-memory arrays with random access in 2026, binary search is almost always better. But the algorithm demonstrates an important principle: match the data structure's access cost model to your algorithm. O(√n) is the optimal solution when forward-jumps are O(1) but backward-seeks are O(n). Understanding the access cost model is a skill that transfers to B-tree design, external merge sort, and streaming algorithms.

The Optimal Jump Size

Why √n? If we use jump size k: - Number of jumps to find the block: n/k - Linear scan within the block: k - Total: n/k + k

Minimise n/k + k: derivative with respect to k → -n/k² + 1 = 0 → k = √n

At k=√n: √n + √n = 2√n jumps total → O(√n).

import math

def jump_search(arr: list, target) -> int:
    n = len(arr)
    step = int(math.sqrt(n))
    prev = 0
    # Jump until arr[min(step,n)-1] >= target
    while arr[min(step, n) - 1] < target:
        prev = step
        step += int(math.sqrt(n))
        if prev >= n:
            return -1
    # Linear search in block [prev, min(step, n))
    while arr[prev] < target:
        prev += 1
        if prev == min(step, n):
            return -1
    return prev if arr[prev] == target else -1

arr = [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377]
print(jump_search(arr, 55))   # 10
print(jump_search(arr, 100))  # -1

Comparison with Other Searches

Complexity Analysis

Time: O(√n) — n/k forward jumps + k linear scan, minimised at k=√n Space: O(1) — no extra space Prerequisite: Array must be sorted

Worst case: Target is just before the last jump → √n jumps + √n linear steps = 2√n

Frequently Asked Questions