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

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}

预期输出：-

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

任何想法将不胜感激。

提前致谢。

Answer 1

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

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

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

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

Answer 2

正如@Rafael Giusti 在编写我们的程序时所说，我们也必须尝试捕获无效输入。

我已经添加了错误处理问题的解决方案（无效情况下数组中的最大元素）。上面的问题可以这样解决，

通过线性搜索（需要 O(n)）
通过二分查找（需要 O(longn)）

线性法

1.Here 对于无效输入我在数组中抛出最大元素

2.And 对于这个问题，我们至少需要数组中的三个元素

注意：我只是检查边缘情况，例如（数组中少于三个元素，数组升序排列，数组降序排列）。您可以完全迭代数组以检查给定数组是否满足条件 - 首先增加 - 然后减少我没有在以下程序中检查过的条件 - 如果不满足边缘情况，我只是返回数组中的最大元素.

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 
}

二分查找法

注意：在无效输入的情况下返回数组中的最大值

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

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

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

c

algorithm

binary-search

data-structures