How Jump Search Works

Imagine searching for a word in a printed dictionary, but you're not allowed to flip open to a random page like Binary Search does — you can only jump forward in fixed-size chunks, like flipping ahead 50 pages at a time. Once you've jumped past where the word should be, you go back one chunk and read through it normally. That's Jump Search — a middle ground between checking everything (Linear Search) and repeatedly halving the search space (Binary Search).

Why Jump Search Exists

Binary Search is fast, but it needs random access to jump straight to any middle index — which works great for arrays, but not as well for data structures where jumping to an arbitrary position is expensive. Jump Search gives you a way to skip through sorted data in bigger strides than Linear Search, without needing the "jump anywhere instantly" ability Binary Search relies on.

How Jump Search Works

1. Pick a block size to jump by — typically √n, which turns out to be mathematically optimal.
2. Jump forward by that block size, checking the value at each jump point.
3. Once you jump to a value larger than the target, you've overshot — the target must be in the previous block.
4. Do a Linear Search within that one block to find the exact value.

Walking Through an Example

Search for 55 in [3, 8, 15, 23, 34, 41, 55, 62, 70, 81] (10 elements, so block size = √10 ≈ 3):

• Jump to index 2: 15 → too small, keep jumping
• Jump to index 5: 41 → too small, keep jumping
• Jump to index 8: 70 → overshot! Target is somewhere in the previous block
• Linear Search backward from index 5 to index 8: index 6 is 55 — found it

Notice this took 3 jumps plus a short linear scan — fewer full comparisons than checking every element from the start, but simpler than Binary Search's repeated halving.

Java Implementation

public class JumpSearch {
    public static int jumpSearch(int[] arr, int target) {
        int n = arr.length;
        int blockSize = (int) Math.sqrt(n);

        int step = blockSize;
        int prev = 0;

        // Jump forward until we overshoot the target or run out of array
        while (prev < n && arr[Math.min(step, n) - 1] < target) {
            prev = step;
            step += blockSize;
        }

        // Linear search within the identified block
        for (int i = prev; i < Math.min(step, n); i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1; // not found
    }

    public static void main(String[] args) {
        int[] arr = {3, 8, 15, 23, 34, 41, 55, 62, 70, 81};
        System.out.println(jumpSearch(arr, 55)); // Output: 6
        System.out.println(jumpSearch(arr, 99)); // Output: -1
    }
}

📝 Note

Why √n specifically? It's the block size that minimizes the total work: jumping in blocks of size b costs about n/b jumps plus up to b elements to linear-scan. Setting b = √n balances both costs — any bigger or smaller block size does strictly more total work.

Time Complexity

⚠️ Complexity Breakdown

Best case: O(1) — target found on the very first jump.
Average / worst case: O(√n)
Space: O(1)

O(√n) sits neatly between O(n) (Linear Search) and O(log n) (Binary Search) — slower than Binary Search, but still a real improvement over checking everything one by one, and useful when jumping to arbitrary positions is more expensive than jumping in fixed, predictable strides.

Common Interview Questions

• Why is √n the optimal block size for Jump Search, rather than some other value?
• How does Jump Search's time complexity compare to Linear Search and Binary Search, and where does it fit in between?
• In what real scenario would Jump Search be preferred over Binary Search?

The Takeaway

Jump Search shows that "sorted data" doesn't force you into a single strategy — you can trade off jump size against scan size depending on what your data structure actually allows. Next up: Interpolation Search, which takes this idea even further by using the actual values in the array to make a smarter guess about where to jump, instead of jumping in fixed-size blocks.

➡️ Next in the Series

Interpolation Search: Guessing Smarter, Not Just Jumping Blindly

Happy learning!
— Team CodeElevateX 🚀