Time Complexity
Best: O(1)
Avg: O(√n)
Worst: O(√n)
Jump Search works on sorted arrays by jumping ahead by fixed steps and then performing a linear search within the identified block.
How it works:
1. Calculate the optimal jump size: √n
2. Jump through the array in blocks until finding a block where the target could be
3. Perform a linear search within that block
4. Return the index if found, -1 otherwise
Time Complexity:
Best: O(1)
Average: O(√n)
Worst: O(√n)
Space Complexity: O(1)
Properties:
- Requires sorted array
- Better than Linear Search, simpler than Binary Search
- Optimal jump size is √n
Jump Search is useful when jumping back is costly (e.g., in linked lists) compared to Binary Search which requires random access.
Related algorithms
Frequently asked questions
- What is Jump Search?
- Jump Search works on sorted arrays by jumping ahead by fixed steps and then performing a linear search within the identified block.
- What is the complexity of Jump Search?
- Time (average): O(√n) · Space: O(1)
- Who is this Jump Search visualizer for?
- The Jump Search visualization targets intermediate-level learners in the Searching category. Useful for students, interview prep, and hands-on review.
- What algorithms are related to Jump Search?
- In the same category (Searching) you can explore: Binary Search, Linear Search, Interpolation Search. Each has an interactive visualization.