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一个测试用例来帮助他们找到代码会失败的地方，但我的测试用例也是无效的。)