algorithm - 为什么二分搜索算法适用于这个一维“寻峰”问题？

Question

我正在研究麻省理工学院关于算法介绍的开放课件第一个类，有些东西对我来说并不是很明显。你不能在24:30开始看讲座here以及一维峰值问题定义和解决方案的所有详细信息的讲义in here
问题是:

for an array of "n" integer elements find a peak

并给出一个大小为 8 的示例数组: example = [6,7,4,3,2,1,4,5] 峰值的定义
对于 example上面的数组 example[1]和 example[7]是“峰值”，因为这些数字大于或等于它们的相邻元素，并且数组最后一个元素的特殊条件适用，它只需要大于或等于它前面的元素。那是:

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

重要观察
从这个例子中，我们可以理解数组可能是未排序的，它可能包含重复项，它可能包含多个峰，根据我的解释，它甚至可能不包含任何单个峰。
到目前为止一切顺利，但当他争辩说在二叉搜索树中拆分数组的定义可以找到一个峰值时，我的麻烦就开始了，** 这对类的每个人来说都非常明显，但对我来说却不是，这似乎是任意的或者我没能理解一些非常重要的事情**
教授去用伪代码定义一个二分搜索算法来找到一个峰值:

我的问题/疑虑

鉴于上述条件 A为什么往左边走？而不是
对？

鉴于上述条件 B为什么向右走？而不是
剩下？

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

该解决方案是否保证对于只有一个“峰值”的情况，我们最初不会丢弃包含该峰值的一半？如果是这样/为什么？

由于数组可以是未排序的并且它可能包含重复项，我不明白哪里可以保证 A 中的 if 条件或 B保持真实，向右或向左寻找都是有意义的，这对我来说似乎是任意的，如果您选择错误，您可以丢弃实际上可能具有唯一峰值的阵列的一半
我错过了什么重要的东西吗？如果是什么？
谢谢大家关注这个问题。

Answer 1

Given the condition above in A why go to the left? instead of the right?

如果你向右走(没有先检查条件 B)，右边的值有很小的概率会继续下降(从左到右)，你不会在那里找到峰值。
但是，在左侧，您知道不会出现这种情况，因为您至少发现了一个更高的值(邻居)，甚至可能是峰值。以下是证明左侧存在峰值的方法(这不是算法的描述；只是一种证明方法):
如果最直接的邻居不是一个峰，那么它左边的下一个可能是。如果没有，那么可能是它左边的下一个......等等。当找到一个峰值或到达最左边的值时，这个系列将结束。如果其他人都不是巅峰，那么这个肯定就是巅峰了。这只发生在值从不减少同时向左看时。
简而言之，无论左边的情况如何，那边的某个地方都有一个高峰，这就是我们在选择边时所需要知道的。

Given the condition above in B why go to the right? instead of the left?

这当然是相同的推理，但镜像。
请注意，您可以决定先检查条件 B，然后再检查 A。当两个条件同时为真时，您实际上可以选择走哪一边。
这就是您感觉选择看起来“任意”的地方。当条件 A 和 B 都为真时，它确实是任意的。
但也要考虑 A 和 B 之一为真而另一个为假的情况。如果你走错了(向下)的方式，你就不能保证值(value)会朝那个方向上升。因此，那一侧没有峰值的可能性很小。
当然，那一侧仍然可能有一个高峰，但既然我们确定另一侧有一个高峰，那么确定无疑是明智的。我们不关心可能会丢弃一些峰，因为我们只需要找到一个峰。

The binary search algorithm assumes we start from a sorted array, so how come it makes sense to apply it to data that may be unsorted?

对特定值的二进制搜索只能在排序数组中工作，但在这里我们不是在寻找特定值。
我们正在寻找的值的条件不那么严格。我们会对任何局部峰值的值感到满意，而不是特定的值。