## Amazon Interview Question

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