c++ - 查找山数组峰值索引的代码

Question

你可能还记得数组 A 是一个山数组当且仅当：A.length >= 3

存在一些i这样0 < i < A.length - 1的：

A[0] < A[1] < ... A[i-1] < A[i]
A[i] > A[i+1] > ... > A[A.length - 1]

注意事项：

• 可以使用arr.get(index)函数及其length = arr.length().
• 它失败的测试用例是：(3,5,3,2,0)。
• 错误：控制到达非 void 函数的末尾。

我的看法：
我想使用二进制搜索（经过一些修改）来找到峰值。记住上面给定的山阵列条件，只有 3 种可能性，即（坡度增加点，峰顶点，坡度下降点）

代码：

int getPeak(MountainArray &arr, int left, int right)
{
  int mid;
  int mid_num;
  int after_mid, before_mid;

  mid = (left + right) / 2;
  if (mid == 0)
  {
    return getPeak(arr, mid + 1, right);
  } // to make sure i dont violate the range of array by calculating before_mid.mid_num = arr.get(mid);
  after_mid = arr.get(mid + 1);
  before_mid = arr.get(mid - 1);

  if (before_mid < mid_num && mid_num < after_mid)
  {
    return getPeak(arr, mid + 1, right);
  }

  else if (mid_num > after_mid && mid_num > before_mid)
  {
    return mid;
  }

  else if (mid_num > after_mid && mid_num < before_mid)
  {
    return getPeak(arr, left, mid - 1);
  }
}

标签： c++arrays

Answer 1

您不初始化mid_num，这会导致未定义的行为。添加：

mid_num = arr.get(mid);  // missing
after_mid = ...
...

顺便说一句，当您找到局部峰值（第二个分支）时，您可能还需要检查它是否也是全局峰值。如所写，它将为此数组返回索引 2: {5,2,4,2,5}，根据您的定义，这不是一座山。