首页 > 代码库 > Search in Rotated Sorted Array II
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.
class Solution {
public:
bool search(int A[], int n, int target) {
if(n==0) return false;
return binary(A,0,n-1,target);
}
bool binary(int A[],int x1,int x2,int target)
{
if(x1>x2) return false;
int m=(x1+x2)/2;
if(A[m]==target) return true;
if(A[x1]<A[x2])
{
if(A[m]<target) return binary(A,m+1,x2,target);
else return binary(A,x1,m-1,target);
}
else
{
return binary(A,x1,m-1,target) || binary(A,m+1,x2,target);
}
}
};
public:
bool search(int A[], int n, int target) {
if(n==0) return false;
return binary(A,0,n-1,target);
}
bool binary(int A[],int x1,int x2,int target)
{
if(x1>x2) return false;
int m=(x1+x2)/2;
if(A[m]==target) return true;
if(A[x1]<A[x2])
{
if(A[m]<target) return binary(A,m+1,x2,target);
else return binary(A,x1,m-1,target);
}
else
{
return binary(A,x1,m-1,target) || binary(A,m+1,x2,target);
}
}
};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。