Amazon Interview Question
Software Engineer / Developersint SearchCircularArray(vector<int>& v ,int m, int num){
if(num > v.at(v.size() - 1)){
return binary_search(v.begin(),(v.end() - m),num);
}else
{
return binary_search(v.end()- m,v.end() -1 ,num);
}
}
int main( )
{
int a [] = {3,4,5,6,1,2};
vector<int> v(a,a+6);
//Here m = 2 , meaning array is circularly shifted by 2 times
//Fist parm:vector
//Second: m
//Third : Elemnt to be searched
cout << SearchCircularArray(v,2,10);
return 0;
}
Please let me know any other better approach than this or if i am missing something
if u dont know how much the array is shifted then also u can do it in O(lgn) time
first step then be to search for a pivote point means the rotated point after that it will be a similar question as given
whole algorithm:
int searchInRotated(int a[],int n,int key)
{
int end=n-1;
int start=0;
int s=0;
int e=n-1;
int mid=0;
if(a[0]>a[n-1])
{
while(s<=e)
{
mid=(s+e)/2;
if(a[mid]>a[mid+1])
break;
else
{
if(a[mid]<a[e])
{
e=mid-1;
}
else
{
s=mid+1;
}}}}
if (mid==0)
{
while(start<=end)
{
mid=(start+end)/2;
if(a[mid]==key)
break;
if(a[mid]>key)
end=mid-1;
else
start=mid+1;
}
return mid;
}
else
{
if(key==a[mid])
return mid;
if(key>=a[mid+1] && key <=a[end])
{
start=mid+1;
while(start<=end)
{
mid=(start+end)/2;
if(a[mid]==key)
break;
if(a[mid]>key)
end=mid-1;
else
start=mid+1;
}
return mid;
}
else
{
end=mid-1;
while(start<=end)
{
mid=(start+end)/2;
if(a[mid]==key)
break;
if(a[mid]>key)
end=mid-1;
else
start=mid+1;
}
return mid;
}
}
}
int main(void)
{
int k;
int a[10]={6,7,8,9,10,1,2,3,4,5};
k=searchInRotated(a,10,10);
printf("position of %d is :%d",a[k],k);
return 0;
}
Lets n = Size(array) - m;
- tito March 28, 2010So check for A[n] >X depending on that you know in which part of array it will be....