Flipkart Interview Question
Software Engineer / DevelopersCountry: 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