二维寻峰二分查找

Question

摘自mit 6.006:在2D数组中找到一个峰值，如果一个数字比它的所有邻居都要>=，那么它就是一个峰值:

• 选择中间列j = m/2
• 查找列j上的全局最大值(i, j)
• 比较(i, j−1)，(i, j)，(i, j + 1)
• 选取(i, j−1)>(i, j)，右
类似如果两个条件都不成立，
• (i, j)为2d峰值
• 用一半的列数解决新问题
• 当你只有一个列时，找到全局最大值，你就完成了。

我理解为什么它可能会找到一个峰值，但我认为它只在数组的一半上找到一个峰值，如果它存在

1. 在这里使用二进制搜索让我感到困惑，因为(1)二维数组没有排序，每次你减半，你基本上是说左边不可能有峰值(这是未确认的?)
2. 查找中间列的最大元素-这忽略了由非最大数形成峰的可能性，或者在该列中可以有多个1D峰
3. 它们比较中间列的max的左右数字——这就忽略了可能在左列和右列中存在大于max但不相邻的元素

谁能给我解释一下为什么这个算法是正确的，希望能解释一下(1)(2)(3)

Answer 1

每次减半就意味着左边不可能有峰值

啊，不，我们说的是是右边的一个峰。左边也可以有峰，但我们不需要找到每一个峰。

为了证明右边有一个峰(不失一般性)，考虑下面的"梯度上升";算法:

1. 从任意数字开始

2. 如果当前数至少有一个大邻居，则选择任意一个大邻居。

这个算法不会循环，因为当前的数字只会增加。这个算法因此终止，因为有有限的数字。当算法终止时，它已经找到了一个峰值。

考虑如果(i, j)在它的列中有最大值，并且我们从(i, j)开始梯度上升会发生什么。(i, j)是一个峰值(太好了!)，或者我们移动到相邻列中的一个更大的数字。在后一种情况下，该数值大于j列的最大值，因此大于j列的所有数值。因此，梯度上升将永远不会重新进入该列，因此它将永远不会进入另一侧的列，这意味着在期望的一侧存在一个峰值。