c - 求数组中先增后减的最大元素

Question

我编写了一个代码并为下面的输入编译它是正确的 作为

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

输出:500

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

输出: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);
   }

但它不适用于

输入:-

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

预期输出:-

15 

但我得到的答案是 16 而不是 15。

任何想法将不胜感激。

提前致谢。

Answer 1

为什么它会起作用？您编写代码时假设数组可以分为两部分:一个增加的部分和一个减少的部分。这个测试用例打破了先决条件。

您可以检查数组是否有效，但在最坏的情况下，它需要线性扫描。最好简单地检查每个元素以找到最大的元素。

例如，检查输入是否正确并不总是好的。对于这个特定问题，如果您想在 O(logN) 中解决它，则必须假设输入是正确的。

(编辑:为了公平起见，这个答案被编辑了。在原来的答案中，我给了 OP 一个测试用例，以帮助他们找到他们的代码会失败的地方，但我的测试用例也是无效的。)