为什么二分搜索算法适用于这个一维“寻峰”问题？
Osc*_*cía 5 algorithm binary-search
我正在研究麻省理工学院关于算法介绍的开放课件第一堂课，有些东西对我来说并不是很明显。你不能开始看在24:30的讲座在这里，并与一维峰值问题定义的所有细节的讲义和解决方案在这里
问题是：
对于“n”个整数元素的数组，找到一个峰值
并给出一个大小为 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或B 保持为真那么向右或向左寻找是有意义的，这对我来说似乎是任意的如果您选择错误，您可以丢弃实际上可能具有唯一峰值的阵列的一半
我错过了什么重要的东西吗？如果是什么？
谢谢大家关注这个问题。
鉴于A中的上述条件，为什么要向左走？而不是右边？
如果您向右移动（不首先检查条件 B），则右侧的值有可能会继续下降（从左到右），并且您不会在那里找到峰值。
然而，在左侧，您知道不可能出现这种情况，因为您已经发现至少一个更高的值（邻居），甚至可能是峰值。以下是证明左侧存在峰值的方法（这不是算法的描述；只是证明的一种方法）：
如果紧邻的峰不是峰，那么其左边的下一个峰可能就是峰。如果没有，那么可能是其左边的下一个......等等。当找到峰值或到达最左边的值时，该系列将结束。如果其他的都不是巅峰，那么这个一定就是巅峰了。仅当向左看时值从未减少时才会发生这种情况。
简而言之，无论左侧的情况如何，左侧的某个地方都会有一个峰值，这就是我们在选择一侧时所需要知道的。
鉴于B中的上述条件，为什么要走右边？而不是左边？
这当然是相同的推理，但是是镜像的。
请注意，您可以决定先检查条件 B，然后再检查条件 A。当两个条件同时成立时，您实际上可以选择走哪一边。这就是你感觉这个选择看起来“任意”的地方。当条件 A 和 B 都成立时，它确实是任意的。
但也要考虑一下 A 和 B 之一为真而另一个为假的情况。如果你走错了（向下）的路，你就不能保证价值会朝那个方向上升。所以那一侧没有峰值的可能性很小。
当然，这一侧仍然可能存在峰值，但由于我们确信另一侧也存在峰值，因此明智的选择是确定性。我们不关心可能会丢弃一些峰值，因为我们只需要找到一个峰值。
二分搜索算法假设我们从一个已排序的数组开始，那么将其应用于可能未排序的数据有何意义呢？
对特定值的二分搜索仅适用于排序数组，但这里我们不是在寻找特定值。我们寻找的值的条件不太严格。我们会对任何局部峰值值感到满意，而不是特定值。