Jump Search

Jump search is the middle ground between a linear scan and binary search. On a sorted array it leaps forward in fixed-size blocks until it sails past the target, then walks back through that one block linearly. The block size floor(sqrt(n)) balances the two phases so the whole thing costs O(sqrt(n)) comparisons — slower than binary search, but it only ever steps forward, which makes it handy when jumping backward is expensive (think a singly linked structure or a magnetic tape).

We search for x = 13 in the sorted array a = [1, 3, 5, 7, 9, 11, 13, 15, 17] (with n = 9, so step = floor(sqrt(9)) = 3). The answer is index 6.

Intuition

Binary search needs random access — it jumps to the middle, then a quarter, then an eighth. Jump search asks for less: it only ever moves forward by a fixed stride. Imagine flipping through a sorted phone book a fixed number of pages at a time. Once you flip past the name you want, you back up to the start of that chunk and read it page by page.

Why sqrt(n)? With a block size b you make about n / b jumps in phase 1 and at most b - 1 steps in phase 2. Their sum n / b + b is smallest when b = sqrt(n), giving roughly 2 * sqrt(n) comparisons total. Any larger block means fewer jumps but a longer linear scan; any smaller means the reverse. The square root is the sweet spot.

Walk through it

Step through the animation on the right. The top pointer block end marks the cell we compare in phase 1; the bottom pointer prev marks the start of the current block (and later the linear cursor).

Phase 1 — jump in blocks. With step = 3, the first block end is a[2] = 5. Since 5 < 13, the target is further along, so prev jumps to 3 and step grows to 6. The next block end a[5] = 11 is also < 13, so prev jumps to 6 and step becomes 9. Now the block end a[min(9, 9) - 1] = a[8] = 17 is not < 13 — we overshot. The target, if it exists, is in the block [6, 8] we just landed on.

Phase 2 — linear scan. Starting at prev = 6, we check a[6] = 13. It is not < 13, so the forward scan stops immediately. The final equality check a[6] == 13 is true, so jump search returns index 6. (If the target were missing, the scan would stop where a[prev] >= x and the equality check would fail, returning -1.)

The code, line by line

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

• Line 3 sets the block size to floor(sqrt(n)) (Python int() truncates). This single choice is what makes the search O(sqrt(n)).
• Line 5 is the phase-1 loop: min(step, n) - 1 is the block-end index, clamped so we never read past the array. We keep jumping while that value is still smaller than x.
• Lines 6–7 commit the jump: prev advances to the old step, and step grows by another block.
• Lines 8–9 are the out-of-range guard: if prev has run off the end of the array, the target is larger than everything, so return -1.
• Line 10 is phase 2: from prev, walk forward one cell at a time while a[prev] is still < x. This scans only the single block we landed in.
• Lines 12–14 do the final equality check. The linear loop stops at the first value >= x; if it equals x we found it, otherwise the target is absent and we return -1.

Complexity

Jump search sits between linear search O(n) and binary search O(log n). It is asymptotically slower than binary search, but it touches memory in a more forward, sequential pattern and never jumps backward by more than one block — which can win on storage where backward seeks are costly.

When to use / pitfalls

Practice