What is Jump Search?
Learn how jump search uses √n block jumps plus a linear scan to search a sorted array, and how to explain it in interviews.
Expected Interview Answer
Jump search finds a target in a sorted array by jumping forward in fixed-size blocks of size √n until it finds a block that could contain the target, then doing a linear scan backward within just that block — running in O(√n) time, which beats linear search but is slower than binary search's O(log n) except when random-access jumps are cheap but comparisons or backward jumps are expensive.
The algorithm jumps through indices 0, √n, 2√n, 3√n, ... comparing arr[jump] against the target, until it finds a block boundary where arr[jump] is greater than or equal to the target (or it runs off the array). It then performs a plain linear scan backward from that boundary through the previous block to find the exact target. The block size √n is chosen because it minimizes the total work: total comparisons is roughly n/step (number of jumps) plus step (size of final linear scan), and n/step + step is minimized when step = √n, giving O(√n) total. It is most useful on systems where jumping backward is more expensive than jumping forward — like a sequential-read-optimized storage device or tape — since it only ever scans forward within each block rather than binary searching, which would require unpredictable back-and-forth access.
- O(√n) time, strictly better than O(n) linear search
- Simpler than binary search — no recursive midpoint logic
- Only needs forward jumps, good for sequential-access storage
- Predictable, cache-friendly forward memory access pattern
AI Mentor Explanation
A scorer flipping through a printed scorecard book to find a specific over does not check every over one by one — they flip forward in fixed chunks, say every 10 pages, checking the over number at each chunk boundary, until they land on a chunk whose starting over exceeds the target. Then they flip backward page by page through just that last chunk to find the exact over. This chunk size is chosen so the number of chunk-jumps plus the size of one chunk's linear flip-through is minimized overall — that balance point is the square root of the book's total overs. It's simpler than repeatedly halving the search range, and it only ever needs forward flipping until the final small backward scan.
Step-by-Step Explanation
Step 1
Choose the block size
Compute step = floor(sqrt(n)), the size of each forward jump.
Step 2
Jump forward in blocks
Advance the pointer by step while arr[min(pointer, n) - 1] is less than the target.
Step 3
Identify the candidate block
Stop jumping once a block boundary value is greater than or equal to the target, or the array bound is reached.
Step 4
Linear scan the block
Scan sequentially from the previous boundary to find the target, returning -1 if not found in the block.
What Interviewer Expects
- Correctly derive why block size √n minimizes total comparisons
- State the overall complexity as O(√n)
- Compare tradeoffs against binary search and linear search explicitly
- Mention the sequential-access-friendly use case as motivation over binary search
Common Mistakes
- Using a block size other than √n and not explaining why that is suboptimal
- Forgetting to bound the final jump to the array length, causing an index-out-of-range error
- Claiming jump search is always faster than binary search (it generally is not for random access)
- Confusing jump search with exponential search — jump search uses fixed steps, exponential search doubles
Best Answer (HR Friendly)
“Jump search finds a target in a sorted array by jumping forward in fixed-size blocks of about the square root of the array's length, then doing a simple linear scan backward within just the block where the target must be. It's slower than binary search in general, but simpler to implement and works well when forward-only sequential access is cheaper than random jumps.”
Code Example
import math
def jump_search(arr, target):
n = len(arr)
step = int(math.sqrt(n))
prev = 0
curr = step
while curr < n and arr[curr - 1] < target:
prev = curr
curr += step
for i in range(prev, min(curr, n)):
if arr[i] == target:
return i
return -1Follow-up Questions
- Why is √n the optimal block size for jump search?
- How does jump search compare to binary search on random-access memory versus sequential storage?
- How would you modify jump search for a two-level (jump of jumps) variant?
- What is the difference between jump search and exponential search?
MCQ Practice
1. What is the time complexity of jump search on a sorted array of size n?
With an optimal block size of √n, total comparisons balance to O(√n), better than linear but worse than binary search.
2. Why is the block size chosen as √n?
The total work is roughly n/step (jumps) plus step (final scan); this sum is minimized when step equals √n.
3. What happens after jump search finds the block that must contain the target?
Jump search finishes with a plain sequential linear scan through the identified block, not a nested binary search.
Flash Cards
What is the optimal block size for jump search on an array of length n? — √n (the square root of n).
What is the time complexity of jump search? — O(√n).
What happens once jump search finds the right block? — A plain linear scan runs backward/forward within just that block to locate the target.
When is jump search preferred over binary search? — When sequential/forward access is cheaper than random access, e.g. on tape or certain streaming storage.