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).
Write a function to determine if a given target is in the array.
The array may contain duplicates.
一刷
题解：
与第33题不同，第33题强调没有duplicate, 重点还要分析时间复杂度。
当left part 不是升序，右边也不是（相等），退化为顺序搜索。
public class Solution {
public boolean search(int[] nums, int target) {
if(nums == null || nums.length == 0) return false;
return search(nums, target, 0, nums.length-1);
}
private boolean search(int[] nums, int target, int lo, int hi){
while(lo<=hi){
int mid = lo + (hi - lo)/2;
if(nums[mid] == target) return true;
if(nums[lo] < nums[mid]){//left part is sorted
if(nums[lo] <= target && nums[mid] > target)
hi = mid - 1;
else lo = mid + 1;
}
else if(nums[mid] < nums[lo]){//right part is sorted
if(nums[mid] < target && nums[hi] >= target)
lo = mid + 1;
else hi = mid - 1;
}
else lo++;
}
return false;
}
}
二刷
思路，代码同上。注意，当nums[lo] == nums[mid]，只能排除掉lo这个点。
比如[1,3,1,1,1], lo = 0, mid = 2.
