C-在阵列中找到最大元素，该数组首先增加然后减小

Question

我制作了一个代码并为下面的输入编译，这是正确的 AS

 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）中求解它。

（ edit ：为了公平地说，该答案是编辑的。在原始答案中，我给了OP测试案例，以帮助他们查找其代码失败的位置，但我的测试案例也无效。）

Answer 2

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

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

解决

1. 通过线性搜索（以O（n）为单位）
2. 通过二进制搜索（占用O（Longn））

线性方法

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

2.我们在此问题中至少需要三个元素

注意：我只是在检查诸如（数组中的少于三个元素，按升序顺序，以降序顺序排列的数组）之类的边缘案例。您可以完全迭代数组，以检查给定的数组是否满足标准 - 首先增加 - 然后减小我在以下程序中未检查的条件 - 如果不满足边缘案例，我只是返回数组中的最大元素。

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