算法设计搜索矩阵

Question

值这个问题不是一门功课，那只是出于个人兴趣，主要我的好奇心

我的教授在课堂上谈到这个问题的一小会儿，但他没有”这件事谈得很多。下面是问题：

给定一个m×n矩阵A，其整数元素分别沿水平方向和垂直方向排列。我需要开发一个递归程序来搜索一个查询值a 是否在A.讨论您的设计的时间复杂性。

所以我想了一会儿。我的第一种方法是检查基本情况：第一个元素和最后一个元素

检查，如果第一个元素>如果最后一个元素<项目

产品，我想找到

什么项目检查这是虚矩阵：（x可以是任何数字，但是这个矩阵是那种垂直和水平方向）

   first  x   x  x   x 
       x  x   x  x   x 
       x  x   mid  x   x 
       x  x   x  x   x 
       x  x   x  x   last 

后，我检查基本情况，并确保“项”我想找到的是这个矩阵的范围之内，我不知道是否从矩阵的“中”（如二分搜索）检查是可以的。如果项目<中，则着重于左半部分。如果项目>中，然后专注于右半部分。

但是，然后我试图让一个矩阵像下面和我的“项目”是10

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

如果我按照我之前说的方式：因为10比中间的“7”时，我专注于正确的部分。然后我检查“8”，因为10大于“8”，我搜索右边的部分。但10是不是在正确的...

任何人都可以给我的想法或见解如何解决这个问题？非常感谢

Answer 1

从左下角开始（在您的示例中为3）。

1. 如果当前值小于您正在搜索的值，则向右转。
2. 如果当前值大于您正在搜索的值，请上去。
3. 如果当前值与您正在搜索的值相同，则返回true。
4. 如果你走出矩阵，返回false。

这是O(n + m)，其中n和m在你的矩阵行和列的数量。这是因为在每一步都完全排除了整行或一列。

Answer 2

最佳解决方案时间是O(1)，并且只是使用散列表跟踪矩阵中的哪些元素。如果空间有问题，也可以使用布隆过滤器。

但是，因为它们已经排序，所以可能不值得添加所有机器。

问题所在寻找的解决方案我认为是O(N)解决方案（其中矩阵的大小为N x N）;从左上角到左下角到右下角，直到找到大于查询的元素为止。然后，通过向右上方蠕动来搜索“级别曲线”，每次执行比较，以查看是否超出或低于查询范围（以正确或上升为准）。

，你可以考虑一下这款另一种方式是保持对每列c窗口lower_c <查询< higher_c的轨道，从左到右。此窗口的尺寸始终为2.