峰值查找算法MIT OCW 6.006-它一直存在吗？

Question

这周我开始了MIT OCW6.006的讲座，在第一节课上教授介绍了找峰算法。

1 2 3 4 5 6 7 8 9
a-i是数字

位置2是峰当且仅当b≥a且b≥c。如果i≥h，位置9是峰值

他提出这个算法是为了提高它的复杂度：

If a[n/2] < a[n/2 − 1] then only look at left half 1 . . . n/2 − − − 1 to look for peak
• Else if a[n/2] < a[n/2 + 1] then only look at right half n/2 + 1 . . . n to look for peak
• Else n/2 position is a peak: WHY?
    a[n/2] ≥ a[n/2 − 1]
    a[n/2] ≥ a[n/2 + 1]

[9,8,7,6,5,2,3,1]

该算法的工作原理如下：

步骤1:A[n/2] 6<7？-->是的，看左半部分[9,8,7,6]
步骤2:A[n/2] 8<9？-->是的，看左半部分[9,8]
步骤3：？？？

我找到了这个相关的问题，但没有答案：找峰算法

Answer 1

您必须自己考虑边界条件。
以下是完整的步骤：

Step 1: a[n/2] < a[n/2-1]? --> 6 < 7? --> yes, look at left half [9,8,7,6]
Step 2: a[n/2] < a[n/2-1]? --> 8 < 9? --> yes, look at left half [9,8]
Step 3: ??? <br>
//if you put a check on boundary condition then
Step 3: a[n/2] > a[n/2+1]? --> 9 > 8? --> yes, look at right half [8]
Step 4: loop terminates as only one element is left(it is a peak)

你可以在这里找到更好的问题描述。