Yatra.com Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Approach:
1. First search for the index of the element which is inverted. Example in the example given array {5,6,7,8,9,10,1,2,3,4} the index is '5' (element 10). Running time (lg n) [Modified binary search]
2. Do an ordinary binary search in the appropriate sub-array.
/*
* Return the index of the highest element in the array
*/
public int searchForBoundry(int[] arr, int start, int end) {
if (start >= end) {
return -1;
}
int mid = start + (end-start)/2;
if (arr[mid] > arr[mid+1]) {
return mid;
}
if (arr[start] < arr[mid]) {
return searchForBoundry(arr, mid, end);
} else {
return searchForBoundry(arr, start, mid);
}
}
/*
* Ordinary Binary Search
*/
public int binarySearch(int[] arr, int start, int end, int element) {
if (start > end) {
return -1;
}
int mid = start + (end-start)/2;
if (arr[mid] > element) {
return binarySearch(arr, start, mid-1, element);
} else if (arr[mid] < element) {
return binarySearch(arr, mid+1, end, element);
}else {
return mid;
}
}
public int searchCircular(int[] arr, int start, int end, int element) {
int index = searchForBoundry(arr, start, end);
if (index != -1) {
if (arr[start] > element) {
return binarySearch(arr, index+1, end, element);
} else {
return binarySearch(arr, start, index, element);
}
} else {
return -1;
}
}
Code for searchForBoundry without recursion
public int searchForBoundry(int[] arr) {
int start=0;
int end=arr.length;
int mid;
if (end<=1) {
return (end-1);
}
while(start < end){
mid = (start + end)/2;
if (arr[mid] > arr[mid+1])
return mid;
if (arr[start] < arr[mid]) {
start = mid;
} else {
end = mid;
}
}
return -1;
}
Modified Binary search will do
- cooldaa January 24, 2012