33. Search in Rotated Sorted Array
参考这个视频. Time = O(log(n)), Space = O(1)
class Solution {
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < nums[left]) { // left half is rotated, right half is sorted
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
} else { // right half is rotated, left half is sorted
if (target < nums[mid] && target >= nums[left]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
}
return -1;
}
}