題目
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
答案
方法1
二分思路
If nums[mid] >= nums[start], we know that nums[start…mid] is definitely sorted
If target is inside start…mid, that would be great, we can just perform a binary search on the interval start…mid
If target is outside of start…mid, meaning it could be greater than nums[mid] or it could be smaller than nums[start]
In this case we reduce the search space from start…end to mid + 1…end
If nums[mid] < nums[start], we know that nums[start…mid] is definitely not sorted, which means nums[mid+1…end] is definitely sorted
If target is inside mid+1…end, that would be great, we can just perform a binary search on the interval mid+1…end
If target is outside of mid+1…end, meaning it could be greater than nums[end] or it could be smaller than nums[mid+1]
In this case we reduce the search space from start…end to start…mid - 1
代碼
class Solution {
public int search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while(l <= r) {
int m = (l + r) / 2;
if(target == nums[m]) return m;
if(nums[l] <= nums[m]) {
if(target >= nums[l] && target <= nums[m]) {
r = m - 1;
}
else {
l = m + 1;
}
}
else {
if(target >= nums[m] && target <= nums[r]) {
l = m + 1;
}
else {
r = m - 1;
}
}
}
return -1;
}
}
方法2
先用binary search找最小元素的index爽雄，以這個index把array分成兩邊芽腾，然后對兩邊分別做binary search
