题目

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请实现一个函数，输入这样的二维数组和一个整数，判断数组中是否含有该整数。
例如下面的数组

1
2
3
4
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15

如果查找 10 ，则返回 true，如果查找 5 ，则返回 false

这个题目之前在leetcode上做过，不过没有做出来，刚开始的思路类似于二分查找，选取当前矩形最中间的数字，如果小于要寻找的整数，则除去左上角的矩形，如果大于要寻找的整数，则去除右下角的矩形，但是之后就没法做了，也没法写成递归的形式。

参考leetcode和「剑指offer」，正确的解法应该是按照左上角或者右下角的数字来逐步缩小搜索范围。以右上角为例，如果查找数字大于右上角数字，则可删除所在行，如果查找的数字小于右上角数字，那么可以删去所在列，重复操作直至找到数字或者矩阵为空。

以上面的矩阵为例，假设我们要查找的数字是 10 ，先从右上角 9 开始，发现 10 > 9，那么删去 9 所在的第一行，得到新矩阵

1
2
3
2 4 9 12
4 7 10 13
6 8 11 15

再看新矩阵右上角数字 12，发现 10 < 12，所以删除 12 所在的列，得到新矩阵

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

再看新矩阵右上角数字 9，10 > 9 ，删除 9 所在行，得到新矩阵

1
2
4 7 10
6 8 11

再看新矩阵右上角数字 10，发现刚好是我们所要查找的数字。

这样我们就找到了所要查找的数字。同样，如果以左下角开始查找也是类似的步骤，如果左下角的数字大于目标数字，那么删除最后一行，如果小于目标数字，则删除第一列，重复操作直至找到数字或者矩阵为空。

Java实现代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix.length == 0) {
        return false;
    }
    int i = 0, j = matrix[0].length - 1;
    // 右上角开始查找
    while (i < matrix.length && j >= 0) {
        if (matrix[i][j] > target) {
            // 删除所在列
            j --;
        } else if (matrix[i][j] < target) {
            // 删除所在行
            i ++;
        } else {
            return true;
        }
    }
    return false;
}

左下角开始查找的代码类似，在这里就不写了。

这个算法用上了辅助空间，空间复杂度是 O(1)，时间复杂度是 O(m*n)，m``n分别是矩阵的长宽。