Skip to main content
Interactive Algorithm Education

Visualize & Master Algorithms & Data Structures

Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.

Search Visualizer

Jump Search

Speed 100ms
Size 15
Difficulty ★★★★★ Beginner
Best For Small or unsorted datasets
Step Progress 0 / 0
Comparisons 0
Target —
Status Ready
Playback Paused
Out of Range
Search Range
Probe / Mid
Found
Step Explanation

Select an algorithm, enter a target value, and click 'Search' to begin.

Pseudocode 
 
 
  
 
 
 When to Use 
 

Select an algorithm to see recommended use cases.

 
 
 
 History 
 

Select an algorithm to see its history.

 
 
 
 
  
 
 
Jump Search
  
 
  Elementary (2/5)
 
~30 minutes   Block-based skipping  √n optimal block size  Linear scan inside one block  Middle ground between linear and binary  
Prereqs: Linear Search, Arrays, Big-O analysis  
 
Quick Reference
Jump Search
Jump Search is an improvement over Linear Search for sorted arrays. It jumps ahead by fixed-size blocks (√n) to find a range containing the target, then performs a linear scan within that block.

Difficulty: Elementary (2/5)
Stablesearching
Complexity
Best Time
O(1)
Average Time
O(√n)
Worst Time
O(√n)
Space
O(1)
When to Use
Works well on sorted arrays when random access is cheap and the dataset is large enough to benefit from skipping elements.
Pros
  • Faster than Linear Search on large sorted arrays
  • In-place, requiring O(1) extra memory
  • Better cache locality than binary search on some hardware
Cons
  • Slower than Binary Search (O(√n) vs O(log n))
  • Only works on sorted arrays
  • Block size choice is fixed to √n regardless of data distribution
History
Jump Search was first proposed in the 1960s as a middle-ground algorithm between Linear Search and Binary Search for sorted arrays.
 
 
Jump Search is the pragmatic middle child between Linear and Binary Search. It doesn’t scan every element, nor does it need binary search’s midpoint machinery.


Instead, it jumps forward in fixed-size blocks until it overshoots the target, then does a small linear scan inside the block that must contain it.


Think of reading a book by flipping ahead a chapter at a time, then scanning that chapter page by page.


How It Works


    

  1. Pick a block size — the optimal is ⌊√n⌋.
    2. 

  2. Jump forward by one block while the block’s end element is still smaller than the target.
    3. 

  3. When a block’s end exceeds (or equals) the target, the target — if present — is inside it.
    4. 

  4. Linearly scan that block; return the index if found, otherwise -1.
    5. 



Key Insight


The √n block size isn’t arbitrary — it’s the answer to a small optimization problem.


    

  • With block size b, jumps cost about n/b and the final linear scan costs up to b.
    • 

  • Total work ≈ n/b + b, minimized when b = √n → O(√n).
    • 



That’s a genuine improvement over O(n) linear search. Because it only walks forward, it also has better cache locality than binary search’s non-contiguous midpoints on some hardware.


Worked Example


Search for 10 in [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] with block size ⌊√10⌋ = 3:


    

  • Jump to index 2: arr[2] = 5 < 10 → continue
    • 

  • Jump to index 5: arr[5] = 11 ≥ 10 → target must be in indices 3–5 ([7, 9, 11])
    • 

  • Linear scan indices 3, 4, 5: 7, 9, then 11 ≠ 10 → not in this block → return -1
    • 



Search for 9 instead: linear scan hits index 4 → return 4. In the visualizer, the cursor leaps by the block size, then creeps forward one position at a time within the final block.


Edge Cases & Pitfalls


    

  • Empty array — return -1 without jumping.
    • 

  • Target at the very start — caught on the first linear scan: best case O(1).
    • 

  • Target beyond the last block — the final jump clamps to the array end; the last partial block gets scanned.
    • 

  • Block size zero — with n = 0, guard against √0 producing a degenerate block.
    • 

  • Not a substitute for binary search — O(√n) is far worse than O(log n) on huge sorted arrays. Jump search wins only when jumps are cheaper than midpoint comparisons.
    • 



Comparison With Other Searches





































ScenarioJump SearchLinear SearchBinary Search
Requires sorted inputYesNoYes
Average timeO(√n)O(n)O(log n)
Cache behaviorSequential-friendlySequentialRandom jumps
Best whenSorted + cheap sequential readsUnsorted / tinyLarge sorted data


Applications


    

  • Sorted data where the storage favors sequential access over random access (e.g., certain disk/tape layouts)
    • 

  • A simple, low-memory improvement over linear search with no recursion or midpoint arithmetic
    • 

  • Educational stepping stone between linear and binary search
    • 



Practice Trajectory


    

  1. Hand-trace Jump Search for target 12 in [2, 4, 6, 8, 10, 12, 14, 16] with block size 2 and with block size 3.
    2. 

  2. Derive why n/b + b is minimized at b = √n.
    3. 

  3. Explain what happens when the target is larger than every element.
    4. 

  4. Compare the number of comparisons for n=100 across linear, jump, and binary search.
    5. 

  5. Implement Jump Search and handle an empty array gracefully.
    6.