为什么二分搜索算法对这个一维“寻峰”问题有效？

Question

我在看麻省理工学院的开放课件的第一次讲座，关于算法的介绍，有一些东西对我来说并不是很明显。你不能在这里观看24:30的讲座和课堂讲稿，这里有一维峰值问题的定义和解决方案的所有细节

问题是：

对于由“n”个整数元素组成的数组，找到一个峰值

example[1] >= example[0] && example[1] >= example[2] #=> is true and therefore a peak
example[7] >= example[6] #=> is true and therefore a peak

我的问题/担心

1. 既然在a中有上述条件，为什么要往左走？而不是右边？
2. 既然在b中有上述条件，为什么要往右边走？而不是左边？
3. 二进制搜索算法假设我们从排序的数组开始，那么将它应用于可能未排序的数据有什么意义呢？
4. 解决方案是否保证，对于只有一个“峰值”的情况，我们最初不会丢弃包含峰值的那一半？如果是，如何/为什么？

由于数组可能是未排序的，并且可能包含重复项，我不明白哪里可以保证如果A或B中的条件为真，那么向右或向左查找都是有意义的，这在我看来是任意的，如果选择错误，可以丢弃数组中实际上可能有唯一峰值的一半

Answer 1

既然上面的条件在A中，为什么要往左走？而不是权利？

如果你去右边（不首先检查条件B)，有一个小概率，在右边的值将继续下降（从左到右），你不会在那里找到一个峰值。

然而，在左边，你知道你不可能有这种情况，因为你已经找到了至少一个更高的值（邻居），甚至可能是一个峰值。以下是如何证明在左侧存在峰值（这不是对算法的描述；只是证明它的一种方法）：

这当然是同样的推理，但也是镜像的。

注意，您可以决定首先检查条件B，然后才检查A。当两个条件同时为真时，您实际上可以选择走哪一边。这就是你从选择看起来“武断”的感觉。当条件A和条件B都为真时，它确实是任意的。

但也要想想A和B中的一个是真的，另一个是假的情况。如果你走错了（向下）的路，你就不能保证价值会朝着那个方向上升。所以有一个小概率，在那一边没有峰值。