取自 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)(3)
最佳答案
each time you halve you are essentially saying there can be no peak on the left
啊，不，我们是说右侧有一个峰。左侧也可以有峰值，但我们不需要找到每个峰值。
为了证明右侧存在峰值(不失一般性)，请考虑以下“梯度上升”算法:
从任意数字开始。
当当前数字至少有一个更大的邻居时，转到任意一个更大的邻居。
该算法永远不会循环，因为当前数字只会增加。该算法因此终止，因为数字是有限的。当算法终止时，它已经找到了峰值。
考虑如果 (i, j) 在其列中具有最大值并且我们在 (i, j) 处开始梯度上升，会发生什么情况。 (i, j) 要么是一个峰值(太棒了!)，要么我们移动到相邻列之一中更大的数字。在后一种情况下，该数字大于 j 列中的最大值，因此大于 j 列中的每个数字。因此，梯度上升永远不会重新进入柱子，因此它永远不会进入另一侧的柱子，这意味着所需一侧存在峰值。
关于arrays - 二维寻峰二分搜索，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/66350187/