为什么二分搜索算法对这个1D“找峰”问题起作用？

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

既然有了上面的条件，为什么要往左走？而不是右派？

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

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

如果它的近邻不是峰，那么它左边的下一个可能是峰。如果不是，那么可能是它左边的下一个...等等。当找到一个峰值或到达最左边的值时，这个系列将结束。如果其他的都不是山峰，那么这一个一定是它。只有当数值在进一步向左看时从未减少时，才会发生这种情况。

简而言之，无论左边的情况如何，那一边的某个地方都有一个顶点，这就是我们在选择一边时所需要知道的一切。

给定B中的上述条件，为什么要向右？而不是左派？

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

而且还要想想A和B中的一个为真，另一个为假的情况。如果你走错了（向下）的路，你就无法保证价值会朝那个方向上升。所以有一个很小的概率，在那一边没有峰值。

当然，那一边可能还有一个高峰，但既然我们确信另一边也有一个高峰，明智的做法是确定无疑。我们不关心潜在地丢弃一些峰，因为我们只需要找到一个峰。

二分搜索算法假设我们从一个排序的数组开始，那么将它应用于可能未排序的数据有什么意义呢？

对特定值的二分搜索只能在排序数组中工作，但这里我们不是在查找特定值。我们要寻找的值的条件不那么严格。而不是一个特定的值，我们将高兴的任何值是一个局部峰值。