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

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

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

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

20 和 90

上面发布的算法只会 return 一个值。不是所有的峰值，甚至不是最大的峰值 - 它只是找到 一些 峰值。