algorithm - 对二维数组进行二分搜索以找到局部最大值？这个算法有什么问题？

Question

这是在矩阵中寻找局部最大值(只有一个)的经典方法。

我的算法是:

• 选择矩阵中心的数字。
• 检查该数字是否为峰值。如果是，则返回。

• 如果没有，请检查左侧和右侧的数字。如果其中一个大于我们当前的数字，则选择矩阵的一半。如果两者都更大，我们可以选择其中一半。

• 重复顶部和底部的数字。这将为我们留下矩阵的一个象限来继续检查。

由于这是对具有 n^2 个元素的 n x n 矩阵的二分搜索，因此应该需要 O(log(n^2)) = O(2*log(n)) = O(log(n))

我很确定这是不正确的，但是我的错误在哪里？

Answer 1

该算法不能保证找到局部最大值。例如，考虑这样一种情况，您需要沿着一条蜿蜒的路径穿过上升值矩阵才能到达峰值。如果该路径在象限之间来回交叉，您的算法将找不到它。

13  1  1  1  1
12  1  1  1  1
11  1  1  2  3
10  1  1  1  4
 9  8  7  6  5

或者，这是一个更简单的示例:

3  1  1  1  1
1  1  1  1  1
1  1  1  1  1
1  1  1  1  1
1  1  1  1  1

从中间开始，如何找到“3”？您的算法没有描述面对水平面时该怎么做。