题目描述（中等难度）

矩阵的每行从左到右是升序， 每列从上到下也是升序，在矩阵中查找某个数。

解法一

看到有序，第一反应就是二分查找。最直接的做法，一行一行的进行二分查找即可。

此外，结合有序的性质，一些情况可以提前结束。

比如某一行的第一个元素大于了 ，当前行和后边的所有行都不用考虑了，直接返回 false。

某一行的最后一个元素小于了 target ，当前行就不用考虑了，换下一行。

时间复杂度的话，如果是 m 行 n 列，就是 。

解法二

参考 这里-Java-solution)，需要很敏锐的观察力了。

数组从左到右和从上到下都是升序的，如果从右上角出发开始遍历呢？

会发现每次都是向左数字会变小，向下数字会变大，有点和二分查找树相似。二分查找树的话，是向左数字变小，向右数字变大。

所以我们可以把 target 和当前值比较。

• 如果 target 的值大于当前值，那么就向下走。
• 如果相等的话，直接返回 true 。

如果 的值小于当前值，也就意味着当前值所在的列肯定不会存在 target 了，可以把当前列去掉，从新的右上角的值开始遍历。

同理，如果 target 的值大于当前值，也就意味着当前值所在的行肯定不会存在 target 了，可以把当前行去掉，从新的右上角的值开始遍历。

看下边的例子。

不管从哪种角度考虑，代码的话都是一样的。

时间复杂度就是每个节点最多遍历一遍了，O(m + n)。

解法三

参考 这里 ，还有一种解法。

我的理解的话，算是一种变形的二分法。

二分法的思想就是，目标值和中点值进行比较，然后可以丢弃一半的元素。

这道题的话是矩阵，如果我们找到矩阵的中心，然后和目标值比较看能不能丢弃一些元素。

我们找到了丢弃元素的原则，可以写代码了。

我们可以用递归的形式去写，递归出口的话，当矩阵中只有一个元素，直接判断当前元素是不是目标值即可。

还有就是分割的时候可能越界，比如原矩阵只有一行，左下角和右下角的矩阵其实是不存在的，按照上边的坐标公式计算出来后，我们要判断一下是否越界。

总

看到有序数组第一反应就是二分了，也就是解法一。

解法二的话，从右上角开始遍历的想法很妙。

解法三的话思想很简单，就是变形的二分法，每次抛弃一部分元素，但代码的话其实写出来不是很容易，相对于解法一和解法二来说是有些复杂度的。

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 查看详情