Input: Array A[0..n-1] without repeat, where A[0]>A[1], A[n-2]<A[n-1].
Output: Find i where A[i-1]>A[i] and A[i]<A[i+1]
Modified binary search can be used here but I am not sure when to select left search space over right. Any ideas?
@samr-1qaz as you know a pics costs more than 1000 words, I will try to explain with picture and you can find the code below
Hope that this will help
int findFall(int[] array) {
if (array.length < 3)
return -1;
int l = 0;
int n = array.length;
int r = n - 1;
while (l < r) {
int mid =(l + r)/2;
if (array[mid] < array[mid + 1] && array[mid] < array[mid - 1]) {
return array[mid];
}
if (array[mid + 1] > array[mid])
r = mid;
else
l = mid + 1;
}
return -1;
}