Find the maximum element in an array which is first increasing and then decreasing

Question

I made a code and compiled for below input it is correct as

 Input: arr[] = {8, 10, 20, 80, 100, 200, 400, 500, 3, 2, 1}

Output: 500

 Input: arr[] = {1, 3, 50, 10, 9, 7, 6}

Output: 50

int findIncre_Decre(int arr[], int low, int high)
  {
        if (low == high)
        return arr[low];

       /* If there are two elements and first is greater then
          the first element is maximum */
         if ((high == low + 1) && arr[low] >= arr[high])
                return arr[low];

         /* If there are two elements and second is greater then
             the second element is maximum */
             if ((high == low + 1) && arr[low] < arr[high])
                 return arr[high];

               int mid = (low + high)/2; /*low + (high - low)/2;*/

          /* If we reach a point where arr[mid] is greater than both of
           its adjacent elements arr[mid-1] and arr[mid+1], then arr[mid]
            is the maximum element*/
       if ( arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1])
            return arr[mid];

       if (arr[mid] > arr[mid + 1] && arr[mid] < arr[mid - 1])
         return findIncre_Decre(arr, low, mid-1);
         else 
        return findIncre_Decre(arr, mid + 1, high);
   }

But it is not working for

Input:-

arr[]={7,8,9,10,15,5,16}

Expected Output:-

15 

But I got answer 16 instead of 15.

Any idea will be appreciated.

Thanks in advance.

Answer 1

As @Rafael Giusti said while writing our program we must try to capture invalid input too.

I have added solution to the problem with error handling (max element in array for invalid case). The above problem could be solved by,

1. By linear search (which takes O(n))
2. By binary search (which takes O(longn))

Linear method

1.Here for invalid input I'm throwing maximum element in the array

2.And we need minimum of three element in an array for this problem

Note : I'm just checking for edge cases like (less than three elements in the array, array in ascending order, array in descending order). You can iterate the array completely to check whether the given array satisfies the criteria - first increasing - then decreasing which I have not checked in the following program - I'm just returning the maximum element in the array if doesn't satisfy the edge cases.

int findElement(int arr[], int low, int high) {
     if(low < 0 || low >= high || low+1 == high) return (arr[low] < arr[high] ? arr[high] : arr[low];
     int max = arr[low];
     for(int i=low+1; i<=high-1 && low-1 <= high; i++) {
         max = arr[i] > max ? arr[i] : max;
         if(arr[i-1] < arr[i] && arr[i] > arr[i+1]) 
            return arr[i];   //Perfect match !!
     }
    return max;    // We haven't found any element 
}

Binary search method

Note: Returned the maximum value in the array case of invalid input

int findElement(int arr[], int low, int high) {
     if(high < low) return arr[low];
     if(high-low < 2) return (arr[low] > arr[high]) ? arr[low] : arr[high];     
     int mid = (low + high)/2;
     int left = findElement(arr, low, mid-1);
     int right = findElement(arr, mid+1, high);
     return (left < arr[mid]) && (right < arr[mid]) ? arr[mid] : (left > right ? left : right);
}