Algorithm Guidecomplexity: O(√n)

Jump Search

Jumps through a sorted array in blocks of size √n to narrow the range fast, then runs a linear search inside the candidate block. The jump cost is higher than binary search, but it wins on storage where moving backward is expensive (magnetic tape, disk).

01Jump Search

Explore How It Works

Starting jump search. With ten values, hop three slots (√n) at a time to find the block that could hold the target 45.

Three slots in, the value is 23, still below 45. It isn't in this block, so hop three more.

The next landing is 56 — past the target. If 45 exists, it is in the block we just skipped over.

Scan that block from its start. The first value, 34, is not the target.

The next value is 45 — a match. End the search.

Search complete · 45 sits at index 4. Three hops plus two scanned values: five comparisons in all.

Live Python

# target: 45

1def jump_search(arr, target):

# n: 10

2 n = len(arr)

# step: √10 ≈ 3

3 step = int(math.sqrt(n))

4 prev = 0

5 while arr[min(step, n) - 1] < target:

6 probe = arr[min(step, n) - 1]

7 prev = step

8 step += int(math.sqrt(n))

9 if prev >= n:

10 return -1

11 while arr[prev] < target:

12 prev += 1

13 if prev == min(step, n):

14 return -1

15 if arr[prev] == target:

16 return prev

17 return -1

1 / 6

02 Understand It Simply

For Everyone

🔑How It Works

Steps ahead √n slots at a time to find the block that could hold the target, then scans that block from its start.

💡In Plain Words

Jumps in √n-sized strides to find a candidate block quickly, then searches it linearly.

Good for media where backward seeks are costly.

📍Where It's Used

–Sorted data
–sequential-access media (tape
–disk)

03 Python Implementation

A clean, readable reference implementation of the core logic of Jump Search.

core_implementation.py

import math

def jump_search(arr, target):
    n = len(arr)
    step = int(math.sqrt(n))
    prev = 0
    while arr[min(step, n) - 1] < target:
        prev = step
        step += int(math.sqrt(n))
        if prev >= n:
            return -1
    while arr[prev] < target:
        prev += 1
        if prev == min(step, n):
            return -1
    if arr[prev] == target:
        return prev
    return -1