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, nums, ..., 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 = , 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.
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) {
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);
}``````