Amazon Interview Question
Software Engineer / Developersint find(int a[], int s, int e)
{
if((e-s)==1)
return e;
int m;
m=(s+e)/2;
if((a[e]-a[m])>0 && (a[m-1]-a[s])>=0)
return m;
if((a[e]-a[m])>0)
return find(a, s, m-1);
else
return find(a,m,e);
}
int main()
{
int a[7]={13,24,35,46,0,4,12};
cout<< find(a,0,6);
return 0;
}
It does not work for {5,8,10,1,2,4,5}
according to your solution it returns the index of 8
you need a check if(a[m]<a[m-1]) return m as soon as you calculate m
This checks for all the cases!! ie if mid value falls on one side along with lower bound or upper bound, then we have to adjust the range as well.
int
main()
{
int a[]={ 4, 5, 6, 7, 8, -1, 0, 1, 2, 3,};
int n=sizeof a/sizeof(int);
int lb=0, hb=n-1, mid;
while(1)
{
mid=(lb+hb)/2;
if(a[mid-1] > a[mid])
break;
if( a[mid] > a[0])
{
lb=mid;
if(a[hb] > a[0]) //make sure we span whole array
hb=n-1;
}
else
{
if(a[lb] < a[0])
lb=0;
hb=mid;
}
}
//print the mid value now
}
This will return the correct output
int rotatedArraySearch (int[] array) {
if (array.length < 1)
return -1;
if (array.length < 2)
return 0;
int start, end, mid;
start = 0;
end = array.length-1;
while(start < end) {
mid = (start+end)/2;
if (a[mid] < a[mid-1])
return mid;
if (a[mid] > a[start])
start = mid+1;
else
end = mid-1;
}
}
Tested, this should work .
- iatbst January 29, 2012