There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= 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 numsafter the possible rotation 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.
nums is an ascending array that is possibly rotated.
-104 <= target <= 104
Solutions
Solution 1: Binary Search
We use binary search to divide the array into two parts, $[left,.. mid]$ and $[mid + 1,.. right]$. At this point, we can find that one part must be sorted.
Therefore, we can determine whether $target$ is in this part based on the sorted part:
If the elements in the range $[0,.. mid]$ form a sorted array:
If $nums[0] \leq target \leq nums[mid]$, then our search range can be narrowed down to $[left,.. mid]$;
Otherwise, search in $[mid + 1,.. right]$;
If the elements in the range $[mid + 1, n - 1]$ form a sorted array:
If $nums[mid] \lt target \leq nums[n - 1]$, then our search range can be narrowed down to $[mid + 1,.. right]$;
Otherwise, search in $[left,.. mid]$.
The termination condition for binary search is $left \geq right$. If at the end we find that $nums[left]$ is not equal to $target$, it means that there is no element with a value of $target$ in the array, and we return $-1$. Otherwise, we return the index $left$.
The time complexity is $O(\log n)$, where $n$ is the length of the array $nums$. The space complexity is $O(1)$.