Monday 11 June 2012

Sorted array rotated unknown times, find an element Interview Question


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.

Time Complexity

O(logn) for  array size is reduced by half every time one enters loop.

7 comments:

  1. Could you please some explanation ?
    Some 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 ?

    ReplyDelete
    Replies
    1. hey ashwin,

      '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.

      Delete
    2. 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.

      Delete
  2. There 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..

    ReplyDelete
  3. Hi 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

    int m= l + (r-l)/2;

    ReplyDelete
  4. Sachin : My solution

    1) 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).

    ReplyDelete
  5. Hi
    I have implemented recursive version of the same algorithm. Please refer to
    Find an element in rotated array

    ReplyDelete