## Flipkart Interview Question

Software Engineer / Developers**Country:**India

**Interview Type:**Phone Interview

how would you find the point of rotation ?

If its linear search. then it defeats the purpose of binary search.

Below is the code to find the point of rotation using binary search

```
private int BinarySearch(int[] a, int start, int end)
{
if(start <= end)
{
int mid = (start + end) / 2;
if(start == end)
return a[mid];
else if(a[mid] > a[mid + 1] && a[mid] > a[mid - 1])
return a[mid];
else if(a[start]>a[mid])
return BinarySearch(a, start, mid - 1);
else
return BinarySearch(a, mid + 1, end);
}
else
return -1;
}
```

Above algorithm fails in this case {1,12,10,8,6,4}

Small change: for last else case in if replace "return BinarySearch(a, mid + 1, end) with BinarySearch(a, mid, end)

Here is a binary search approach

```
boolean find(arr,start,finish,data)
{
if(start==finish)
{
if(arr[start]==data)
return true;
return false;
}
if(start==finish-1)
{
if(arr[start]==data || arr[finish]==data)
return true;
return false;
}
else
{
mid=(start+finish)/2;
if(arr[mid]==data)
return true;
if(arr[mid]>arr[start])
{
if(data>=arr[start] && data<arr[mid])
find(arr,start,mid-1,data);
else
find(arr,mid+1,finish,data);
}
else
{
if(data>arr[mid] && data<=arr[finish])
find(arr,mid+1,finish,data);
else
find(arr,start,mid-1,data);
}
}
}
```

Please comment if any corner cases are left.

public static int rotated_binary_search(int A[], int N, int key) {

int L = 0;

int R = N - 1;

while (L <= R) {

// Avoid overflow, same as M=(L+R)/2

int M = L + ((R - L) / 2);

if (A[M] == key) return M;

// the bottom half is sorted

if (A[L] <= A[M]) {

if (A[L] <= key && key < A[M])

R = M - 1;

else

L = M + 1;

}

// the upper half is sorted

else {

if (A[M] < key && key <= A[R])

L = M + 1;

else

R = M - 1;

}

}

return -1;

}

Just find the index at which the rotation occurred say: X, i.e. 6 7 8 1 2 3 4 5 so X = 3. Now do normal binary search but use following function to manipulate indexes of array in an non rotated sorted array:

So when u set low = 0; high = N, it will return you low = 3 and high = 2 which is exactly the mapping in actual array. Use modified indexes to perform normal binary search.

- Anonymous October 31, 2011