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

Question

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

我的算法是：

• 选择矩阵中心的数字。
• 检查数字是否为峰值。如果是，return.

• 如果不是，请检查左右两边的数字。如果其中一个大于我们当前的数字，则选择矩阵的那一半。如果两者都较大​​，我们可以选择一半。

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

由于这是对具有 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'？你的算法没有描述面对水平面时该怎么做。

Answer 2

考虑阅读 Find a peak element in a 2D array，其中描述了一种蛮力方法，以及一种时间复杂度为 O(rows * log(columns)) 的有效方法，在您的情况下 O(nlogn)。

该算法基于二进制搜索，因此 logn 您的复杂度也有：

1. 考虑中间列并找到其中的最大元素。
2. 设mid列的index为‘mid’，mid中最大元素的值 列为“max”，最大元素位于“mat[max_index][mid]”。
3. If max >= A[index][mid-1] & max >= A[index][pick+1], max是一个peak, return最大
4. 如果 max < mat[max_index][mid-1]，对矩阵的左半部分重复。
5. 如果 max < mat[max_index][mid+1]，重复矩阵的右半部分。

---

但是，您的算法不会适用于所有情况，并且可能无法找到局部最大值，因为您只查看当前中心的相邻元素，而这不会保证你会找到最大值（当然元素没有排序）。示例：

1 1 1 1 1
1 1 1 1 1
1 2 1 1 1
1 1 1 1 1
1 1 1 1 10

你从中心开始，你选错了子矩阵，你注定找不到局部最大值。