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，与I不同的是，这次存在重复元素
class Solution {
public:
bool search(vector<int>& nums, int target) {
int res=-1;
int l=0;
int r=nums.size()-1;
int mid=0;
while(l<=r)
{
int mid=l+(r-l)/2;
if(nums[mid]==target)
return true;
else if(nums[l]<nums[mid]) //mid左边是顺序
{
if(nums[l]<=target&&nums[mid-1]>=target)
r=mid-1;
else
l=mid+1;
}
else if(nums[l]>nums[mid]) //mid右边是顺序
{
if(nums[mid+1]<=target&&nums[r]>=target)
l=mid+1;
else
r=mid-1;
}
else //不确定左边是否为重复，只能往前一步
l++;
}
if(nums[mid]==target)
return true;
else
return false;
}
};
leetcode No81. Search in Rotated Sorted Array II
原文：http://blog.csdn.net/u011391629/article/details/52138430