用于搜索矩阵中的值的算法设计

Question

这个问题不是作业,只是出于个人兴趣,主要是我的好奇心

我的教授在课堂上谈了这个问题一段时间,但他没有多说这个.以下是问题:

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

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

检查第一个元素>项目是否检查最后一个元素<item

项目是我想要找到的

这是假想矩阵:(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

在检查基本情况并确保我想要找到的"项目"在此矩阵的范围内之后,我不知道是否可以从矩阵中的"mid"进行检查(如二进制搜索).如果item <mid,则将焦点放在左半边.如果item> mid,则将焦点放在右半边.

但是,然后我尝试制作一个像下面这样的矩阵,我的"项目"是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位数.这是因为在每个步骤中,您完全排除了整个行或列.