python - 为什么 peak1d 不会错过峰值(如果存在)？

Question

我在here中看到了peak1d算法和 Peak finding algorithm .

我不明白为什么它一定会找到峰值(如果存在)。似乎我们决定去一半，而另一半可能会错过一个高峰。我不明白你怎么可以对随机数组应用“二进制搜索”技术(该数组没有先验属性)。

我如何证明如果在 a 中至少有一个峰，以下算法将找到其中一个峰。

import random
a = [random.randint(0,100) for i in xrange(10)]

def peak1d(a,i,j):
    m = (i+j)/2
    if a[m-1] <= a[m] >= a[m+1]:
        return m
    elif a[m-1] > a[m]:
        return peak1d(a,i,m)
    elif a[m]<a[m+1]:
        return peak1d(a,m+1,j)


print a[peak1d(a,0,len(a))]

Answer 1

案例 1，a[m-1] <= a[m] >= a[m+1] , 我们有一个峰值。

案例 2，a[m-1] > a[m] ，假设我们沿着列表走，向左走。我们可能会在一段时间内找到越来越高的元素，但最终会发生以下两种情况之一:

1. 我们找到一个小于或等于我们刚刚查看的元素的元素。那么刚刚过去的那个就是一个峰顶。

2. 我们点击了列表的开头。那么第一个元素就是峰。

因此，列表的前半部分在某处有一个峰值，我们可以只看那一半。我们不需要考虑下半场。

情况 3 等同于情况 2。我们只需要考虑列表的后半部分，同理。

请注意，您对寻峰算法的实现是错误的。它没有正确处理列表的端点。