## Amazon Interview Question

Software Engineer / Developers```
int 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....