peakFinder的划分与征服方法

Question

分而治之的方法在寻找峰的过程中起了很大作用

find_peak(a,low,high):
    mid = (low+high)/2
    if a[mid-1] <= a[mid] >= a[mid+1] return mid // this is a peak;
    if a[mid] < a[mid-1] 
        return find_peak(a,low,mid-1) // a peak must exist in A[low..mid-1]
    if a[mid] < a[mid+1]
        return find_peak(a,mid+1,high) // a peak must exist in A[mid+1..high]

所以我的问题是，如果我们使用这个算法，我们可能会松开另一半的峰值可能实际存在。

还是假设我们发现的峰是一个峰，另一半是另一个峰，因此在一个数组中可能有两个峰。

Answer 1

我将使用它作为峰值定义：“如果数组元素不小于其邻居，则它就是峰值。”

这个数组有两个峰值元素：

[10, 20, 15, 2, 23, 90, 67]

20和90

上述算法只返回一个值。不是所有的峰值，甚至不是最大的峰值-它只是找到的一些峰值。