为什么peak1d不会错过一个峰，如果它存在的话？

Question

我在here和Peak finding algorithm中看到了peak1d算法。你知道吗

我不明白，如果它存在，为什么它肯定会找到一个峰值。看来我们决定只走一半，而另一半可能会错过一个高峰。我不明白你怎么能对一个随机数组应用“二进制搜索”技术（数组没有先验属性）。你知道吗

我怎样才能证明if there is at least one peak in是the following algorithm will find one of the peak。你知道吗

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。我们只需要考虑清单的后半部分，根据同样的理由。你知道吗

请注意，峰值查找算法的实现是错误的。它不能正确处理列表的端点。你知道吗