二维数组中的查找问题(三种方法)

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

二维数组为array[][]，整数位target
一开始我想的是先从行判断，当target>array[i]并且target<array[i+1]的时候，那么就可以确定在这一行里面，后来还报了数组越界，因为后面的i+1可能越界
解决了越界错误，依然不对，因为可能有[3,5,7] [4,6,8]这种情况，5不在最小为4的那一行里面

所以只需要满足target>array[i]即可，然后通过for循环遍历

方法一

public class Solution {
    public boolean Find(int target, int [][] array) {
    //判定特殊情况
        if(array.length==0)return false;
        if(array[0].length==0)return false;
       /
        for(int i=0;i<array.length;i++){
            if(target==array[i][0])return true;
            //target>第一个数，就进入循环
            if(target>array[i][0]){
                for(int j=1;j<array[i].length;j++){
                    if(target==array[i][j])return true;
                }
            }
        }
        return false;
    }
}
时间是164ms，当然会慢，因为这比简单的双重for循环只加了一个简单的判定，效率高不了多少

方法二

相对于第一种，增加了在单行中查找的技巧——二分查找，注意二分查找要用while循环，保证不断二分，而且low<=high
时间是154ms,快了一些

public class Solution {
    public boolean Find(int target, int [][] array) {
        int r=array.length;
        int l=array[0].length;
        if(r==0||l==0)return false;
        for(int i=0;i<array.length;i++){
            if(target>=array[i][0]){
                //low与high作为下标，必须在数组的bound里面，否则会数组越界
                int low=0;
                int high=l-1;
                //这里要小于等于,因为可能存在一开始两者就相同的情况
                while(low<=high){
                    int mid=(low+high)/2;
                    if(target>array[i][mid])low=mid+1;
                    else if(target<array[i][mid])high=mid-1;
                    else return true;
                }
            }
        }
        //当找不到对应的数的时候，就输出false
        return false;
    }
}

方法三：

考虑充分利用条件
左上为最小，右下为最大
左下为行最大，列最小，右上为行最小，列最大
所以找到左下或右上这种属性相反的情况
然后让target进行判定，比如找左下**，如果target大，列就加，taget小，行就减**
把大小和行列分别对应起来，就简单多了

public class Solution {
    public boolean Find(int target, int [][] array) {
        int r=array.length;
        int l=array[0].length;
        if(r==0||l==0)return false;
        //初始情况，找左下方的点
        int i=r-1;
        int j=0;
       // 防止数组越界
        while(i>=0&&j<l){
            if(target>array[i][j])j++;
            else if(target<array[i][j])i--;
            else return true;
       }
        //当找不到对应的数的时候，就输出false
        return false;
    }
}

时间为152ms