81.Search in Rotated Sorted Array II
Follow up for “Search in Rotated Sorted Array”: What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
这是上面那道题的后续题目，这次出现了重复元素，不过出现了重复元素，主要思路没有变化，还是通过寻找有序区间并判断target是否存在于这个区间来调整low，high两个指针的位置。
但是这次有重复元素了，所以A[mid]和A[high]的大小关系并不能成为我们判断左半边还是右半边有序的条件了，比如给出数组{1,2,3,3,3,3,3},旋转之后可能是{3,3,3,3,3,1,2}或者{3,1,2,3,3,3,3}，这样，我们仅凭中间值和边缘值的大小关系是不能判断出哪边有序的，所以解决方案是如果中间值和边缘值相等，则high–然后判断中间值和新的边缘值的关系。
注意这里移动high指针会造成算法时间复杂度的变化，最坏的情况就是整个数组都由一个数字组成，那就要移动到low=high为止，也就是算法时间复杂度从O(lg n）变成了O(n)
代码如下:
class Solution {
public:
bool search(vector<int>& nums, int target) {
int size=nums.size(),low=0,high=size-1,mid=0;
while(low<=high){
mid=low+(high-low)/2;
if(target==nums[mid])
return true;
if(nums[mid]<nums[high]){
if(target>nums[mid]&&target<=nums[high])
low=mid+1;
else
high=mid-1;
}
else if(nums[mid]>nums[high]){
if(target>=nums[low]&&target<nums[mid])
high=mid-1;
else
low=mid+1;
}
else
high--;
}
return false;
}
};