我在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))]
最佳答案
案例 1,a[m-1] <= a[m] >= a[m+1]
, 我们有一个峰值。
案例 2,a[m-1] > a[m]
,假设我们沿着列表走,向左走。我们可能会在一段时间内找到越来越高的元素,但最终会发生以下两种情况之一:
我们找到一个小于或等于我们刚刚查看的元素的元素。那么刚刚过去的那个就是一个峰顶。
我们点击了列表的开头。那么第一个元素就是峰。
因此,列表的前半部分在某处有一个峰值,我们可以只看那一半。我们不需要考虑下半场。
情况 3 等同于情况 2。我们只需要考虑列表的后半部分,同理。
请注意,您对寻峰算法的实现是错误的。它没有正确处理列表的端点。
关于python - 为什么 peak1d 不会错过峰值(如果存在)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23004137/