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.
Hide Tags
这个是在 前一道的基础上改过来的，主要是 left middle right 相同的时候，递归为左右部分的并，其他部分不变：
class Solution {
public:
bool search(int A[], int n, int target) {
if(n==) return A[]==target?true:false;
return help(A,,n-,target);
}
int help(int* & A,int l,int r,int &target)
{
if(target<A[l]&&target>A[r]) return false;
if(target==A[l]) return true;
if(target==A[r]) return true;
if(r-l==) return false;
int m = (l+r) /;
if(target==A[m]) return true;
if(A[l]<A[m]){
if(A[l]<target&&target<A[m]) return help(A,l,m,target);
return help(A,m,r,target);
}
else if(A[l]>A[m]){
if(A[m]<target&&target<A[r]) return help(A,m,r,target);
return help(A,l,m,target);
}
else{
return help(A,l,m,target)||help(A,m,r,target);
}
}
};