二维数组中的查找

1.题目：
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
2.考察点：
数组，二分查找
3.思路：
方法一：暴力求解
遍历二维数组中的每一个数，找到后返回true
时间复杂度为O(n2);空间复杂度为O(1)

public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array.length==0||array[0].length==0)//排除数组为空或者第一行为空格的情况
            return false;
        for(int i=0;i<array.length;i++){//行数
            for(int j=0;j<array.length;j++){//列数
                if(array[i][j]==target)//找到
                    return true;
            }
        }
        return false;
    }
}

方法二：二分查找
时间复杂度：O(m+n) ，其中m为行数，n为列数，最坏情况下，需要遍历m+n次。
空间复杂度：O(1)
对于方法一，此题有额外信息没有利用上，数组从左到右递增，从上到下递增。有序的数组很显然应该想到二分。

1）我么设初始值为右上角元素，arr[0][5] = val，目标tar = arr[3][1]
2）接下来进行二分操作：
3）如果val == target,直接返回
4）如果 tar > val, 说明target在更大的位置，val左边的元素显然都是 < val，间接 < tar，说明第 0 行都是无效的，所以val下移到arr[1][5]
5）如果 tar < val, 说明target在更小的位置，val下边的元素显然都是 > val，间接 > tar，说明第 5 列都是无效的，所以val左移到arr[0][4]
6）继续步骤2）
相当于一横一竖的扫描，不断缩小范围
从右上角开始

public class Solution {
    public boolean Find(int target, int [][] array) {
       int row=0;
       int col=array[0].length-1;//很明显我们从右上角开始
        while(col>=0&&row<array.length){
            if(array[row][col]==target){
            return true;
        }else if(array[row][col]>target){//如比目标值大，说明很可能在本行，则在本行左移
            --col;
        }else if(array[row][col]<target){//如比目标值小，说明在下面的行，则本列下移
            ++row;
        }
      }
      return false;  
    }
}

从左下角开始

public class Solution {
    public boolean Find(int target, int [][] array) {
       int row=array.length-1;
       int col=0;//很明显我们从左上角开始
        if(row==0){
            return false;
        }
        while(col<array.length&&row>=0){
            if(array[row][col]==target){
            return true;
        }else if(array[row][col]>target){//如比目标值大，说明在上一行
            --row;
        }else if(array[row][col]<target){//如比目标值小，说明在本行，右移
            ++col;
        }
      }
      return false;  
    }
}