【剑指】二维数组中的查找

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

[

[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]

]

给定 target = 7，返回 true。

给定 target = 3，返回 false。

这个矩阵有这样的特征：

 左下角和右上角相对于左上角和右下角具备优势，因为一个方向增大，一个方向减小，可以逐步移动。

以查找数字7为例：

第一步，右上角数字是9， 9 > 7 ，则一定不会在最后一列了，因为9下方的数字都比9大，只可能在9的左侧，那么剔除第4列。

第二步，右上角数字是8， 8 > 7 ，则一定不会在这一列了，因为8下方的数字都比8大，只可能在8的左侧，那么剔除第3列。

第三步，右上角数字是2，2 < 7，那么数字7很可能存在2的下方或者右侧，但是右侧的列都被踢除了，所以只能在2的下方。2左侧的值都比2小，因此剔除第1行。

第四步，右上角数字是4，4 < 7，那么数字7很可能存在4的下方或者右侧，但是右侧的列都被踢除了，所以只能在4的下方。4左侧的值都比4小，因此剔除第2行。

第五步，右上角数字是7，7 = 7，找到了。

我们发现如下规律: 首先选取数组中右上角的数字。如果该数字等于要查找的数字，查找过程结束; 如果该数字大于要查找的数字，剔除这个数字所在的列;如果该数字小于要查找的字，剔除这个数字所在的行。

右上角搜索：

    public boolean Find(int target, int [][] array) {
        if (array == null || array.length < 0 || array[0].length < 0){
            return false;
        }
        
        int rows = array.length;
        int cols = array[0].length;
        
        int row = 0;
        int col = cols - 1;
        
        while (row <= rows - 1 && col >= 0){
            if (array[row][col] == target){
                return true;
            } else if (array[row][col] > target){
                col--;
            } else {
                row++;
            }
        }
        
        return false;
    }

左下角搜索：

    public boolean Find(int target, int [][] array) {
        if (array == null || array.length < 0 || array[0].length < 0){
            return false;
        }
        
        int rows = array.length;
        int cols = array[0].length;
        
        int row = rows - 1;
        int col = 0;
        
        while (row >= 0 && col <= cols - 1){
            if (array[row][col] == target){
                return true;
            } else if (array[row][col] > target){
                row--;
            } else {
                col++;
            }
        }
        
        return false;
    }