给定一个由 N 2 个不同整数组成的 N×N 数组 a，设计一个 O(N) 算法来找到一个局部最小值：一对索引i和j使得：
a[i][j] < a[i+1][j]a[i][j] < a[i-1][j]a[i][j] < a[i][j+1]a[i][j] < a[i][j-1]我在一本在线算法书籍《Java 编程简介》第 4.2 章：排序和搜索中找到了这个问题。
它类似于问题 35（同一页）：
a[i-1] < a[i] < a[i+1]）。它有某种基于二进制搜索的解决方案，我无法找到。
Robert Sedgewick 和 Kevin Wayne的网络版书籍 Algorithms 中也提到了同样的问题。（参见“创造性问题”部分，问题 19）。
作者在该链接中给出的问题提示是：
在第 N/2 行中找到最小值，检查列中的邻居 p 和 q，如果 p 或 q 更小，则在该一半中重复出现。
更好的方法是：在第 N/2 行中找到最小值，检查其列中的所有条目，如果我们在列中获得较小的条目，则在较小的列条目所属的行中重复出现。
例如。对于下面的数组，N=5：
1 12 3 1 -23
7 9 8 5 6
4 5 6 -1 77
7 0 35 -2 -4
6 83 1 7 -6
第 1 步：中间一行是 [ 4 5 6 -1 77]。IE。行号 3。
第 2 步：当前行中的最小条目是-1。
第 3 步：最小条目（即-1）的列邻居是5和-2。-2是最小的邻居。它在第 4 行。
继续执行步骤 2-3，直到我们得到本地 min。
编辑：
例如@anuja 的评论中提到的 （主要问题是 n×n 数组。这个输入是 3×4 数组，但我们可以使用它）：
1 2 3 4
5 1 6 -1
7 3 4 -2
第 1 步：中间一行是[5 1 6 -1]。IE。行号 2。
第 2 步：当前行中的最小条目是-1。
第 3 步：最小条目（即-1）的列邻居是4和-2。
-2是最小列邻居。它在第 3 行。
迭代到第 2 步：-2 在其行中最小，在其相邻列中最小。所以我们以 -2 作为局部最小值的输出结束。
更新：这个答案是假设边不是局部最小值，因为它们不是由原始问题陈述中的四个比较定义的。在这种情况下，这个答案是正确的（不可能）。如果您重新定义问题以使边缘可以是局部最小值，则每个矩阵都至少包含一个局部最小值 - 因此您可以使用分而治之的方法。
如果边缘单元不能是局部最小值：
上述问题没有解决方案。一个 N×N 数组需要 O(N^2) 时间来读取元素。由于矩阵中的任何地方都可能有一个局部最小值“隐藏”，因此可以证明这是必要的。
如果您打算要求 O(N^2) 算法，那么简单地遍历每个元素并将其与其 4 个邻居进行比较需要 O(N^2) 时间。
要么你记错了面试问题（还有更多问题），要么这只是一个微不足道的编码练习。
证明：
1. Construct a NxN matrix such that each cell has the value M[i,j] = N*i + j.
2. Select a random x,y (1 < x < N and 1 < y < N) and assign M[x,y] = -1
该矩阵只有一个局部最小值 (M[x,y])，其位置与其他单元格中的值无关。因此，其他单元格不提供有关其位置的信息，因此不可能有任何系统来搜索它，它的搜索结果优于预期的 (N^2/2) 个单元格 = O(N^2)。
（换句话说，你也可以搜索一个几乎全为零的矩阵 M[i,j] = 0 除了 M[x,y] = -1 的最小值。）
这个证明取决于能否在步骤 1 中构造一个没有局部最小值的矩阵。 如果边缘单元可能是局部最小值，那么每个矩阵都必须有一个，并且这个证明不再成立。
访问一个随机单元格。如果它的四个邻居中的任何一个具有较小的值：转到该单元格。如果没有一个邻居更小，则您处于局部最小值。如果可能具有相同值的单元格，则避免循环会有点困难。
更新：
我们可以选择最小的邻居，而不是访问一个邻居。
最困难的拓扑似乎是两个“同心”螺旋的情况，其中一个充当螺旋堤。在最坏的情况下，这仍然需要大约 N/2 步。（N=细胞数。）