[LeetCode] 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.

Hide Tags

Array Binary Search

 

  这个是在 前一道的基础上改过来的,主要是 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);
}
}
};
上一篇:WPF XAML 资源样式模板属性存放位置


下一篇:Kudu 常见的几个应用场景