arrays - 多峰一维峰发现算法

目前，我指的是麻省理工学院开放式课件的视频教程中给出的在一维数组中寻找峰值的解释。
https://www.youtube.com/watch?v=HtSuA80QTyo
递归关系：T(n)=T(n/2) + O(1)只强调数组的一半，加上它将产生一个峰值作为输出什么可以是递归关系说多峰确实存在。
请有人澄清一下这个问题。
提前谢谢！

最佳答案

视频中的问题是：在一维数组中找到一个峰值，其中A[0...N-1]是A[i]或A[i] >= A[i-1] and A[i] >= A[i+1]或i = 0 and A[i] >= A[i+1]时的峰值一个数组可能有许多峰值，请注意，您只需要给出任何一个峰值这个问题可以用分而治之的算法来解决。我在i = N-1 and A[i] >= A[i-1]中实现了它。

// it return the index of the peak.
//it can contain many peak, you can return Any One.

int find_a_peak(int a[], int low, int hi) {
   if (low == hi) return low;
   if (low == hi - 1) return a[low] > a[hi] ? low : hi;
   int mid = (low + hi) / 2;
   if (a[mid] >= a[mid+1]) {
     //At least one peak can be found in the subarray A[low,low+1,...,mid]
     return find_a_peak(a, low, mid);
   } else {
     //At least one peak can be found in the subarray A[mid+1,...,hi]
     return find_a_peak(a, mid+1, hi);
   }
}

实际上，这种算法和二进制搜索是一样的你可以在每一步把数组切成一半大小即C，这样T(N) = T(N/2) + O(1)）。

关于arrays - 多峰一维峰发现算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26943750/