738. Jump Search Using Recursion

Given a sorted array nums (non-decreasing) and an integer target, implement Jump Search recursively to find the index of target. Jump Search works by moving forward by fixed-size blocks (typically sqrt(n)) until it finds a block whose last element is >= target, then performing a linear (or recursive) scan inside that block. Return the index of target if found, or -1 otherwise. For test cases where the array contains duplicates of target, the answer is the FIRST index at which target appears.

Input: A sorted integer array nums and an integer target.

Output: Return an integer index, or -1 if target is not in nums.

Examples

Input: [1,2,3,4,5,6,7,8,9,10], 7
Output: 6
Explanation: 7 is at index 6.

Input: [2,4,6,8,10], 5
Output: -1
Explanation: 5 is not present.

Input: [1], 1
Output: 0
Explanation: Single-element array containing the target.

Constraints

• 1 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• nums is sorted in non-decreasing order
• -10^9 <= target <= 10^9

Asked by