二维数组的查找

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

例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7, 则返回true; 如果查找数字5, 由于数组不含有该数字，则返 回false。

{ 1, 2, 8, 9 }
{ 2, 4, 9, 12 }
{ 4, 7, 10, 13 }
{ 6, 8, 11, 15 }

解题思路：当我们需要解决一个复杂的问题时，一个很有效的办法就是从一个具体的问题入手，通过分析简单具体的例子，试图寻找普遍的规律。针对这 个间题，我们不妨也从一个具体的例子入手。下面我们以在题目中给出的 数组中查找数字7为例来一步步分析查找的过程。

具体思路：从数组的一个角上选取数字来和要查找的数字做比较

首先我们选取数组右上角的数字9。由于9大于7,并且9还是第4列的第一个（也是最小的）数字，因此7不可能出现在数字9所在的列。于是我们把这一列从需要考虑的区域内剔除，之后只需要分析剩下的3列。第3列的8情况与第四列的9相同，所以可以剔除，第二列的2比我们要找的7小，这时我们就需要将行+1，以此类推，当刚好处于7时，结果便出来了。

解法一：按例题中的从右上角开始

public static boolean findNumFromRight(int[][] matrix, int rows, int clomuns, int num) {
    if (matrix == null || rows < 0 || clomuns < 0) {
        return false;
    }
    // 从右上角开始 如果右上角的比要找的数大 则列-- 反之 则行++
    int row = 0;
    int clomun = clomuns - 1;
    boolean isFound = false;
    while (row < rows && clomun >= 0) {

        if (matrix[row][clomun] == num) {
            isFound = true;
            break;
        }
        if (matrix[row][clomun] > num) {
            // 右上角第一个大于我们要找的
            --clomun;
        } else {
            ++row;
        }

    }
    return isFound;
}

解法二：选取左下角的数字

public static boolean findNumFromLeft(int[][] matrix, int rows, int clomuns, int num) {
    if (matrix == null || rows < 0 || clomuns < 0) {
        return false;
    }
    // 从左下角开始 如果左下角的比要找的数大 则行-- 反之 则列++
    int row = rows - 1;
    int clomun = 0;
    boolean isFound = false;
    while (clomun < clomuns && row >= 0) {

        if (matrix[row][clomun] == num) {
            isFound = true;
            break;
        }
        if (matrix[row][clomun] > num) {
            // 左下角第一个大于我们要找的
            --row;
        } else {
            ++clomun;
        }

    }
    return isFound;
}

需要注意的是，我们不能选择左上角或者右下角，因为这样就不符合我们找出来的规律了。

测试main方法：

public static void main(String[] args) {
    int[][] matrix = {
            { 1, 2, 8,  9  },
            { 2, 4, 9,  12 },
            { 4, 7, 10, 13 },
            { 6, 8, 11, 15 }
    };

    System.out.println("row:" + matrix.length + " column:" + matrix[0].length);
    boolean isRightFound = findNumFromRight(matrix, matrix.length, matrix[0].length, 7);
    System.out.println("findNumFromRight " + isRightFound);

    boolean isLeftFound = findNumFromLeft(matrix, matrix.length, matrix[0].length, 7);
    System.out.println("findNumFromLeft " + isLeftFound);
}

这题看上去复杂，但是如果发现了规律，则很简单了。

总结上述查找的过程：

首先选取数组中右上角的 数字。 如果该数字等于要查找的数字， 查找过程结束；如果该数字大于要 查找的数字， 剔除这个数字所在的列：如果该数字小于要查找的数字， 剔除这个数字所在的行。

也就是说如果要查找的数字不在数组的右上角， 则每一次都在数组的查找范围中剔除一行或者一列， 这样每一步都可以缩小 查找的范围， 直到找到要查找的数字， 或者查找范围为空。