There is an integer array nums sorted in ascending order (with distinct values), which has been possibly rotated at an unknown pivot index k such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]].
For example, [0, 1, 2, 4, 5, 6, 7] might be rotated at pivot index 3 to become [4, 5, 6, 7, 0, 1, 2].
Given the array nums and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Array: [4, 5, 6, 7, 0, 1, 2] Target: 0 -> index 4
Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0 Output: 4 Explanation: 0 is at index 4 in the rotated array.
Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3 Output: -1 Explanation: 3 is not in the array.
1 <= nums.length <= 5000-10^4 <= nums[i] <= 10^4nums are distinct.nums is an ascending array that is possibly rotated.-10^4 <= target <= 10^4nums = [4, 5, 6, 7, 0, 1, 2], target = 0