題目要求：在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。

思路：每次都選取數(shù)組查找范圍內(nèi)的 右(左)上角 數(shù)字，若該數(shù)字大于要查找的數(shù)字，則剔除該數(shù)字所在列(行)； 若該數(shù)字小于要查找的數(shù)字，則剔除該數(shù)字所在行(列)。一步一步縮小查找范圍，直到找到該數(shù)字

代碼實(shí)現(xiàn):

/**
 * 問(wèn)題類(lèi)型：二維數(shù)組 
 *
 *  時(shí)間復(fù)雜度：O(M + N)
 *  空間復(fù)雜度：O(1)
 */
public class FindEleInTwoDimeArray {

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

        boolean hasFound = false;  // 是否找到目標(biāo)數(shù)字標(biāo)記
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return hasFound;
        }

        int row = matrix.length; // 二維數(shù)組的行
        int col = matrix[0].length; // 二維數(shù)組的列(行的列數(shù))

        //int rowStart = 0, colStart = col - 1; // 從數(shù)組的右上角開(kāi)始
        int rowStart = row - 1, colStart = 0; // 從數(shù)組的左下角開(kāi)始

        // 在二維數(shù)組的范圍內(nèi)
        while (rowStart < row && colStart >= 0) {

            /**
             * 從左下角開(kāi)始找
             */
            if (matrix[rowStart][colStart] == target) {
                hasFound = true;
                break;
            } else if (matrix[rowStart][colStart] > target) {
                rowStart--; // 向上移動(dòng)
            } else {
                colStart++; // 向右移動(dòng)
            }

            /*// 判斷數(shù)組右上角數(shù)字與目標(biāo)數(shù)字是否相等
            if (matrix[rowStart][colStart] == target) {
                hasFound = true;
                break;
                // 大于則縮小列的范圍
            } else if (matrix[rowStart][colStart] > target) {
                colStart--; // 向左移動(dòng)
                // 小于則縮小行的范圍
            } else {
                rowStart++; // 向下移動(dòng)
            }*/
        }

        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("二維數(shù)組如下所示:");
        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("輸入要查找的數(shù)字：");
        Scanner input = new Scanner(System.in);
        int target = input.nextInt();
        System.err.println("是否找到: " + find(null, target)); // 輸入空指針，健壯性測(cè)試
        System.err.println("是否找到: " + find(matrix, target)); // 輸入數(shù)組包含的數(shù)字
        System.err.println("是否找到: " + find(matrix, target)); // 輸入數(shù)組不包含的數(shù)字
    }
}