为什么二进制搜索算法适用于这个一维“寻峰”问题？
Why does the binary search algorithm works for this 1D" Peak finding" problem?
我正在研究麻省理工学院关于算法介绍的开放课件第一堂课，有些东西对我来说不是很明显。您不能在 24:30 here and the lecture notes with all the details of the 1D peak problem definition and solution 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
重要观察
从这个例子我们可以看出数组可能是未排序的，它可能包含重复项，它可能包含多个峰，根据我的解释，它甚至可能不包含任何单个峰。
到目前为止一切顺利，但当他争辩说在二叉搜索树中拆分数组的定义可以找到一个峰值时，我的麻烦就开始了，** 这对每个人来说都非常明显 class 但对我来说不是，这似乎是武断的或者我没能理解一些非常重要的事情**
教授用伪代码定义了一个二分查找算法来寻找峰值：
我的questions/concerns
- 鉴于
A中的上述条件，为什么要向左走？而不是
对吧？
- 鉴于
B中的上述情况，为什么要向右走？而不是
离开了？
- 二分搜索算法假定我们从排序数组开始，那么将其应用于可能未排序的数据有何意义？
- 解决方案是否保证在只有一个“峰”的情况下我们最初不会丢弃包含峰的那一半？如果是 how/why?
由于数组可以是未排序的并且它可能包含重复项我不明白在哪里可以保证如果 A 或 B 中的条件保持为真它有意义去寻找右边或左边，这对我来说似乎是任意的，如果你选择错误，你可以丢弃实际上可能具有唯一峰值的数组的一半
我是不是漏掉了什么重要的东西？如果是什么？
Given the condition above in A why go to the left? instead of the right?
如果你向右走（不首先检查条件 B），右边的值很可能会继续下降（从左到右），你不会在那里找到峰值.
但是，在左侧，您知道不会出现这种情况，因为您已经找到至少一个更高的值（相邻值），甚至可能是峰值。以下是如何证明左侧存在峰值（这不是算法的描述；只是证明它的一种方法）：
如果最近的邻居不是峰，那么它左边的下一个可能是。如果没有，那么可能是它左边的下一个……等等。当找到峰值或到达最左边的值时，该系列将结束。如果其他 none 是峰，那么这就是它。只有当向左看得更远时值从未减少时才会发生这种情况。
简而言之，不管左边是什么情况，那一边那里的某处有一个峰，这就是我们在选择边时需要知道的。
Given the condition above in B why go to the right? instead of the left?
这当然是同一个推理，只是镜像而已。
请注意，您可以决定先检查条件 B，然后才检查条件 A。当两个条件同时为真时，您实际上可以选择去哪一边。
这就是您从中感觉到选择看起来“任意”的地方。当条件A和B都为真时确实是任意的。
但也要想想A和B其中一个为真另一个为假的情况。如果你走错了（向下）的路，你就无法保证价值会朝那个方向上升。所以那一侧没有峰的可能性很小。
当然，可能在那一侧有一个峰，但是因为我们确定other 一边，为确定而去是明智的。我们不关心可能会丢弃一些峰，因为我们只需要找到一个峰。
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?
对特定值的二分搜索只适用于排序数组，但这里我们不是在寻找特定值。
我们正在寻找的值的条件不太严格。我们将对 任何 局部峰值值感到满意，而不是特定值。
这是查看在每个中点如何做出决定的一种方法。
想象一下，你去树林里徒步旅行，在小径上走了一会儿后，你意识到你想爬一座山峰。在开始寻找之前，您知道要到达顶峰，您需要爬上斜坡。以下是故事的其余部分（在一维世界中）的结局 -
- 您先向左看（或向右看，如果您愿意的话）。
- 如果地面在您的左侧较高，您可以走上那个斜坡。只要一直往坡上走，就是在爬坡，一定能登顶。不管是大还是小。
- 如果地面偏左，则说明您在斜坡上。你不想去那里。于是，你转身向右看，希望能找到一个山峰。
- 如果右边的地面较高，你就往那个方向走，这样你就会接近一个山峰
- 如果地面也向右倾斜，那么你已经在山顶上了
我正在研究麻省理工学院关于算法介绍的开放课件第一堂课，有些东西对我来说不是很明显。您不能在 24:30 here and the lecture notes with all the details of the 1D peak problem definition and solution 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
重要观察 从这个例子我们可以看出数组可能是未排序的，它可能包含重复项，它可能包含多个峰，根据我的解释，它甚至可能不包含任何单个峰。
到目前为止一切顺利，但当他争辩说在二叉搜索树中拆分数组的定义可以找到一个峰值时，我的麻烦就开始了，** 这对每个人来说都非常明显 class 但对我来说不是，这似乎是武断的或者我没能理解一些非常重要的事情**
教授用伪代码定义了一个二分查找算法来寻找峰值：
我的questions/concerns
- 鉴于
A中的上述条件，为什么要向左走？而不是 对吧？ - 鉴于
B中的上述情况，为什么要向右走？而不是 离开了？ - 二分搜索算法假定我们从排序数组开始，那么将其应用于可能未排序的数据有何意义？
- 解决方案是否保证在只有一个“峰”的情况下我们最初不会丢弃包含峰的那一半？如果是 how/why?
由于数组可以是未排序的并且它可能包含重复项我不明白在哪里可以保证如果 A 或 B 中的条件保持为真它有意义去寻找右边或左边，这对我来说似乎是任意的，如果你选择错误，你可以丢弃实际上可能具有唯一峰值的数组的一半
我是不是漏掉了什么重要的东西？如果是什么？
Given the condition above in A why go to the left? instead of the right?
如果你向右走（不首先检查条件 B），右边的值很可能会继续下降（从左到右），你不会在那里找到峰值.
但是，在左侧，您知道不会出现这种情况，因为您已经找到至少一个更高的值（相邻值），甚至可能是峰值。以下是如何证明左侧存在峰值（这不是算法的描述；只是证明它的一种方法）：
如果最近的邻居不是峰，那么它左边的下一个可能是。如果没有，那么可能是它左边的下一个……等等。当找到峰值或到达最左边的值时，该系列将结束。如果其他 none 是峰，那么这就是它。只有当向左看得更远时值从未减少时才会发生这种情况。
简而言之，不管左边是什么情况，那一边那里的某处有一个峰，这就是我们在选择边时需要知道的。
Given the condition above in B why go to the right? instead of the left?
这当然是同一个推理，只是镜像而已。
请注意，您可以决定先检查条件 B，然后才检查条件 A。当两个条件同时为真时，您实际上可以选择去哪一边。 这就是您从中感觉到选择看起来“任意”的地方。当条件A和B都为真时确实是任意的。
但也要想想A和B其中一个为真另一个为假的情况。如果你走错了（向下）的路，你就无法保证价值会朝那个方向上升。所以那一侧没有峰的可能性很小。
当然，可能在那一侧有一个峰，但是因为我们确定other 一边，为确定而去是明智的。我们不关心可能会丢弃一些峰，因为我们只需要找到一个峰。
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?
对特定值的二分搜索只适用于排序数组，但这里我们不是在寻找特定值。 我们正在寻找的值的条件不太严格。我们将对 任何 局部峰值值感到满意，而不是特定值。
这是查看在每个中点如何做出决定的一种方法。
想象一下，你去树林里徒步旅行，在小径上走了一会儿后，你意识到你想爬一座山峰。在开始寻找之前，您知道要到达顶峰，您需要爬上斜坡。以下是故事的其余部分（在一维世界中）的结局 -
- 您先向左看（或向右看，如果您愿意的话）。
- 如果地面在您的左侧较高，您可以走上那个斜坡。只要一直往坡上走，就是在爬坡，一定能登顶。不管是大还是小。
- 如果地面偏左，则说明您在斜坡上。你不想去那里。于是，你转身向右看，希望能找到一个山峰。
- 如果右边的地面较高，你就往那个方向走，这样你就会接近一个山峰
- 如果地面也向右倾斜，那么你已经在山顶上了