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


  • 0
    S

    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?


  • 0

    @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

    0_1475660478678_zadacha.png

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

  • 0
    S

    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.


  • 0

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


Log in to reply
 

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