在次线性时间内搜索二维数组

Question

今天我在面试中被问到以下问题：

给定一个n行n列的整数数组，不包含重复的值，并且从左到右以及从上到下的值递增，提供一种算法来检查给定的值是否在数组中。

我提供的答案类似于这个线程中的答案：
算法：在二维整数数组中高效搜索整数的方法？

这个解决方案的时间复杂度为O(2n)，我认为这是最优解。

然而，面试官告诉我，可能可以用次线性时间解决这个问题。我已经想破了头，但是却没有任何思路。

是否有次线性解决方案，或者这是最优解？

- the_james_marq

---

这是一个详尽讨论的副本，对吧？https://dev59.com/pHE95IYBdhLWcg3wGqAH - justhalf

只是为了明确，您的输入大小为n^2，使得2n相对于输入大小是次线性的。您的面试官不仅仅是观察这个事实，是吗？ - foxcub

@justhalf 哇，那里的答案，我们真的认为 O(n+m) 或 O(N * log(M/N)) 会是最好的吗？ - clwhisk

你的数组几乎是有序的。它们的拓扑结构有点奇怪。尝试适应二分查找来处理它。 - le-doude

在这里对问题进行了彻底的分析：http://twistedoakstudios.com/blog/Post5365_searching-a-sorted-matrix-faster。 - Raymond Chen

被接受的答案不是错误的吗？ - foxcub

Answer 1

要问自己的问题是，每个比较给你什么信息？它可以让你消除矩形“左上方”或“右下方”的区域。

假设在'x'处进行比较，告诉你正在寻找的内容更大：

XXX... XXX... XXx... ...... ......

其中：

'x' - 检查过的空间

'X' - 检查显示这不是您的数据可能位于的位置

'.' - 仍未知

您必须以聪明的方式使用此信息来检查整个矩形。

假设您在中间列上按二进制搜索方式进行比较...

您将获得一个结果如下：

XXX... XXX... XXX... XXXXXX ...XXX ...XXX

留下了两个半宽和可能是全高的矩形空间。您可以如何利用这些信息？

我建议通过'.'的2个子矩形进行递归处理。但是，现在不选择中间列，而是选择中间行来进行二进制搜索。

因此，N乘以M矩形的最终运行时间如下所示：

T（N，M）= log（N）+ T（M/2，N）*2

请注意，由于递归堆栈在检查列和行之间切换，因此索引发生了变化。最终运行时间（我没有费心解决递归）应该是类似于T（M，N）= log（M）+log（N）的东西。

- DanielV

---

是的...在对角线上进行二分查找，然后对右上方和左下方的两个块进行递归。 - clwhisk

这个问题也在这里讨论过：https://dev59.com/pHE95IYBdhLWcg3wGqAH，它的时间复杂度不是`O(log n)，而是O(N * log(M/N))`。 - justhalf

我认为这个算法实际上更像是 Mlog(N) + Nlog(M)，但我还不完全确定。虽然如此，考虑到限制条件，我怀疑是否有更好的方法可用。 - DanielV

假设矩阵的每个块都选择“中心”元素。那么您的递归公式变为T(n) = 2*T(n/2) + log(n)。这不是亚线性的。 - foxcub

我猜你回答的真正问题是，你定义的递归并没有像你希望的那样解决为log(M) + log(N)，而是与原始定义无关。 - foxcub