Sorted array has been rotated unknown times, find an element in it
Amazon Interview (April 2012)
Problem Statement
A sorted array has been rotated for unknown no of times, find an element in it in O(logn). Write production ready and bug free code.Ex if {2,4,6,8,10} is rotated 2 times it becomes{6,8,10,11,2,4}
Solution
#include<stdio.h>
int find(int a[], int l, int r, int x);
int main()
{
int arr[6] = {6,8,10,11,2,4};
printf("%d", find(arr,0,5,2));
scanf("%d", arr[0]);
}
int find(int a[], int l, int r, int x) {
while(l <= r) {
int m = (l+r)/2;
if(a[m] == x) return 1;
if(a[l] <= a[m]) {
if(x > a[m])
l = m+1;
else if(x >= a[l])
r = m-1;
else l = m+1;
}
else {
if (x < a[m])
r = m-1;
else if (x <= a[r])
l = m+1;
else r = m-1;
}
}
return 0;
}
//If you have a different approach in mind, please share it in comments section for our readers.
int find(int a[], int l, int r, int x);
int main()
{
int arr[6] = {6,8,10,11,2,4};
printf("%d", find(arr,0,5,2));
scanf("%d", arr[0]);
}
int find(int a[], int l, int r, int x) {
while(l <= r) {
int m = (l+r)/2;
if(a[m] == x) return 1;
if(a[l] <= a[m]) {
if(x > a[m])
l = m+1;
else if(x >= a[l])
r = m-1;
else l = m+1;
}
else {
if (x < a[m])
r = m-1;
else if (x <= a[r])
l = m+1;
else r = m-1;
}
}
return 0;
}
//If you have a different approach in mind, please share it in comments section for our readers.
Could you please some explanation ?
ReplyDeleteSome comments in the code explaining what each variable is.. I presume l is left and r is right and x is the number to find but why have to chosen l as 0 and r as 5 ?
hey ashwin,
Delete'l' and 'r' are left index and right index of array and you are right 'x' is the number to find. So now it would be clear 'l' is 0 for 0 is the left index of array and as array is of size 6, so 5 would be right index i.e. (array.length-1).
And please notice that if-else condition themselves explains all the cases. So I avoided comments.
Thanks a lot Sachin. I figured it out just after I wrote the comment yesterday. I worked through the program and it became clear immediately.
DeleteThere is a bug in the code...how do you predetermine the position of the smallest element in the sorted array....for example in your case the 5th number is smallest...but if the smallest number is positioned in the last slot of array, then to find the number you have to traverse the array in O(n) time..
ReplyDeleteHi Sachin, at this step int m = (l+r)/2; there will be integer overflow. This happens when l+r exceeds integer limit, one way to avoid this is
ReplyDeleteint m= l + (r-l)/2;
Sachin : My solution
ReplyDelete1) Find the position until which the array is rotated --> O(logn).
2) Split the array into two arrays with the position (which we found out in step 1) as the divider.
3) Apply binary search on both these arrays -> O(logn).
Hi
ReplyDeleteI have implemented recursive version of the same algorithm. Please refer to
Find an element in rotated array