Jump Search
Problem
Jump Search is a searching algorithm for sorted arrays that works by jumping ahead by fixed steps and then performing a linear search within a smaller range.
Examples:
Example 1:
Input: arr = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610], target = 55
Output: 10
Explanation: Jump Search first jumps ahead by √16 = 4 steps until it finds a value greater than 55, then performs a linear search in the previous block to find 55 at index 10.
Example 2:
Input: arr = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20], target = 18
Output: 8
Explanation: Jump Search jumps ahead by √10 ≈ 3 steps until it finds a value greater than 18, then performs a linear search to find 18 at index 8.
Solution
Intuition
- Jump Search works on the principle of skipping some elements to reduce the number of comparisons.
- It jumps ahead by a fixed step size, and when it finds a value greater than the search element, it performs a linear search in the previous block.
- The optimal jump size is √n, where n is the size of the array.
- Jump Search is faster than Linear Search but slower than Binary Search.
Approach
- Determine the block size to jump (typically √n).
- Jump from index 0 to block size, then to 2*block size, and so on until finding a value greater than the search element or reaching the end of the array.
- Once a value greater than the search element is found, perform a linear search in the previous block.
- If the element is found, return its index; otherwise, return -1.
Complexity Analysis
- Time Complexity: O(√n) where n is the number of elements in the array.
- Space Complexity: O(1) as it only uses a constant amount of extra space.
Implementation
CPP
Run your code to see output here