There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Example 3:
Input: nums = [1], target = 0
Output: -1
Constraints:
1 <= nums.length <= 5000-104 <= nums[i] <= 104- All values of
nums are unique. nums is guaranteed to be rotated at some pivot.-104 <= target <= 104
Idea:
Binary Search: the idea is to create a recursive function that takes l and h as range in input and the key.
1) Find middle point mid = (l + h)/2
2) If key is present at middle point, return mid.
Edge case check(not found): if (l > h) return -1;
3) Else If nums[l..mid] is sorted
a) If key to be searched lies in range from nums[l]
to nums[mid], recur for nums[l..mid].
b) Else recur for nums[mid+1..h]
4) Else (nums[mid+1..h] must be sorted)
a) If key to be searched lies in range from nums[mid+1]
to nums[h], recur for nums[mid+1..h].
b) Else recur for nums[l..mid]
Solution:
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function(nums, target) {
return searching(nums, 0, nums.length - 1, target);
};
function searching(nums, l, h, target) {
// basic case: not found
if (l > h) return -1;
let mid = Math.floor((l + h) / 2);
// basic case: found
if (target === nums[mid]) return mid;
// if nums[l...mid] is sorted
if (nums[l] <= nums[mid]) { /// make sure is <=
if (target >= nums[l] && target <= nums[mid])
return searching(nums, l, mid - 1, target);
else
return searching(nums, mid + 1, h, target)
}
// if nums[l...mid] is notesorted, then nums[mid+1..h] must be sorted
if (target >= nums[mid] && target <= nums[h])
return searching(nums, mid + 1, h, target);
else
return searching(nums, l, mid - 1, target);
}
