algorithm - 亚线性时间内的二维数组搜索

Question

今天在一次采访中被问到以下问题：

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

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

这个解决方案是 O(2n)，我认为这是最佳解决方案。

然而，面试官随后告诉我，可以在亚线性时间内解决这个问题。我已经绞尽脑汁思考如何去做这件事，但我一无所获。

亚线性解决方案是否可能，或者这是最佳解决方案？

Answer 1

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

假设您在“x”处进行比较，它会告诉您您正在寻找的东西更大：

XXX...
XXX...
XX X ...
……
……

'x' - 检查空间
'X' - 检查表明这不是您的数据的可能位置
'.' - 还是一个未知数

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

假设您以这种方式在中间列上进行二进制搜索...

你会得到类似的结果

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

剩下两个矩形空间的一半宽度和可能的全高。你能用这些信息做什么？

我建议在 '.' 的 2 个子矩形上重复出现。 但是，现在不是选择中间列，而是选择中间行来进行二进制搜索。

因此，N x M 矩形的最终运行时间看起来像 T(N, M) = log(N) + T(M/2, N)*2

请注意索引的变化，因为您的递归堆栈在检查列和行之间切换。最终运行时间（我没有费心解决递归）应该是 T(M, N) = log(M) + log(N) （可能不完全是这样，但它会相似）。