1. There is an integer array nums sorted in ascending order (with distinct values). 2. 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]. 3. 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. 4. You must write an algorithm with O(log n) runtime complexity.
Input Format
Input is managed for you
Output Format
Output is managed for you
Constraints
1 <= nums.length <= 5000 -10^4 <= nums[i] <= 10^4 All values of nums are unique. nums is guaranteed to be rotated at some pivot. -10^4 <= target <= 10^4
Notice
Try First, Check Solution later
1. You should first read the question and watch the question video.2. Think of a solution approach, then try and submit the question on editor tab.3. We strongly advise you to watch the solution video for prescribed approach.Example
Input
7 4 5 6 7 0 1 2 1
Output
5