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.
Given the array nums after a possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not.
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
1 <= nums.length <= 5000All values are unique.One side of the mid is always sorted — determine which side and check if target is in that range.
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
// Left half is sorted
if (nums[left] <= nums[mid]) {
if (target >= nums[left] && target < nums[mid]) right = mid - 1;
else left = mid + 1;
} else { // Right half is sorted
if (target > nums[mid] && target <= nums[right]) left = mid + 1;
else right = mid - 1;
}
}
return -1;
}Time: O(log n) · Space: O(1)