二维数组中的查找

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

思路：每次都选取数组查找范围内的 右(左)上角 数字，若该数字大于要查找的数字，则剔除该数字所在列(行)； 若该数字小于要查找的数字，则剔除该数字所在行(列)。一步一步缩小查找范围，直到找到该数字

代码实现:

/**
 * 问题类型：二维数组 
 *
 *  时间复杂度：O(M + N)
 *  空间复杂度：O(1)
 */
public class FindEleInTwoDimeArray {

    private static boolean find(int[][] matrix, int target) {

        boolean hasFound = false;  // 是否找到目标数字标记
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return hasFound;
        }

        int row = matrix.length; // 二维数组的行
        int col = matrix[0].length; // 二维数组的列(行的列数)

        //int rowStart = 0, colStart = col - 1; // 从数组的右上角开始
        int rowStart = row - 1, colStart = 0; // 从数组的左下角开始

        // 在二维数组的范围内
        while (rowStart < row && colStart >= 0) {

            /**
             * 从左下角开始找
             */
            if (matrix[rowStart][colStart] == target) {
                hasFound = true;
                break;
            } else if (matrix[rowStart][colStart] > target) {
                rowStart--; // 向上移动
            } else {
                colStart++; // 向右移动
            }

            /*// 判断数组右上角数字与目标数字是否相等
            if (matrix[rowStart][colStart] == target) {
                hasFound = true;
                break;
                // 大于则缩小列的范围
            } else if (matrix[rowStart][colStart] > target) {
                colStart--; // 向左移动
                // 小于则缩小行的范围
            } else {
                rowStart++; // 向下移动
            }*/
        }

        return hasFound;
    }

    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("二维数组如下所示:");
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                System.out.print(matrix[i][j] + "   ");
            }
            System.out.println();
        }
        System.out.print("输入要查找的数字：");
        Scanner input = new Scanner(System.in);
        int target = input.nextInt();
        System.err.println("是否找到: " + find(null, target)); // 输入空指针，健壮性测试
        System.err.println("是否找到: " + find(matrix, target)); // 输入数组包含的数字
        System.err.println("是否找到: " + find(matrix, target)); // 输入数组不包含的数字
    }
}