← Back to Home
Jump Search
A searching algorithm for sorted arrays. The basic idea is to check fewer elements by jumping ahead by fixed steps.
Visualization
Step 1 / 10
Speed:
Details
Analogy
Imagine finding a page in a book. Instead of flipping one page at a time (linear search), you jump forward by chapters. Once you jump past the page you're looking for, you go back to the previous chapter and flip pages one by one to find it.
Purpose
To find a target in a sorted array by jumping ahead in blocks, and then performing a linear search in the identified block. It's a compromise between linear and binary search.
Use Cases
Better than linear search, but not as good as binary search. It can be useful in systems where jumping back is expensive.
Algorithm Steps
Line 1
1
step = sqrt(n)
2
prev = 0
3
while arr[min(step, n)-1] < target:
4
prev = step
5
step += sqrt(n)
6
if prev >= n: return -1
7
while arr[prev] < target:
8
prev++
9
if prev == min(step, n): return -1
10
if arr[prev] == target: return prev
11
return -1
Current
Executed
Pending
Explanation
What's Happening?
Step 1/10
Search for target 55. Array length is 12, so jump step is sqrt(12) ≈ 3.
Updates with each step • Clickfor full view
Code Implementation
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