04-二维数组中的查找

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 1 2 8 9 2 4 9 12 4 7 10 13 6 8 11 15

最容易想到的就是暴力算法，两层循环依次比较，时间复杂度O(n)。 结合题中给的条件，每一行和每一列是递增有序，我们考虑二分查找和分治算法的思想，通过逐渐缩小范围来降低时间复杂度。 这里注意一下如果我们从左上角开始查找，那么很难去掉部分区域，导致很复杂，如果我们从右上角开始查找，那么每一次比较都可以去掉一部分区域，从而减少问题的规模。 举个例子，查找7，首先和右上角的9比较，7<9，所以需要在前三列查找，这样问题规模就缩小了；然后和8比较， 7<8，所以需要在前两列查找；继续和2比较，7>2，所以需要在前两列中的后三行查找，继续和4比较....直到找到7或者数组越界查找失败。 代码仅供参考。

 public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0){
            return false;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        for (int i = 0, j = col - 1; i < row && j >= 0;) {
            int num = matrix[i][j];
            if (num == target) {
                return true;
            } else if (num < target) {
                i++;
            }else {
                j--;
            }
        }
        return false;
    }