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.
与I类似，只是在二分搜索前，只是在判断左右两边是否有序时更加麻烦一些。
此时复杂度是O(n)了，和采用线性搜索的方法基本一致
class Solution {
public:
bool search(int A[], int n, int target) {
int left=;
int right=n-;
int mid;
while(left<=right)
{
mid=(left+right)/;
if(A[mid]==target)
{
return true;
}
//增加了这些判断语句
bool isLeft=true;
for(int i=left;i<=mid;i++)
{
if(A[i]>A[mid])
{
isLeft=false;
break;
}
}
if(isLeft)
{
if(A[left]<=target&&target<A[mid])
{
right=mid-;
}
else
{
left=mid+;
}
}
else
{
if(A[mid]<target&&target<=A[right])
{
left=mid+;
}
else
{
right=mid-;
}
}
}
return false;
}
};