# Array A[0..n-1] without repeat, where A[0]>A[1], A[n-2]<A[n-1]

• 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;
}``````

• Thanks for answering. Sorry don't follow the diagram, can you explain with few words? I am not able to understand why there cannot exist and array where such an index i cannot exist.

• @samr.1qaz you can read the code in case you don't understand the fugure

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.