A list nums of different numbers was sorted from small to large. Then it may have been rotated around some pivot: a part from the end was moved to the front. For example, [10,20,30,40,50,60] can become [40,50,60,10,20,30]. The list may also be left as it is, with no rotation.
You are given the list after this step, and a number target. Return the index of target in nums. If target is not in the list, return -1.
Your solution must run in O(log n) time.
Examples
Example 1:
Input: nums = [40,50,60,10,20,30], target = 20
Output: 4
Explanation: 20 is at index 4.
Example 2:
Input: nums = [40,50,60,10,20,30], target = 35
Output: -1
Explanation: 35 is not in the list.
Example 3:
Input: nums = [5,6,7,8], target = 8
Output: 3
Explanation: This list was not rotated. 8 is at index 3.