题目描述

那么如果将每一行依次展开，形成一个nm长度的一维数组，这个数组整体都是递增的，可以进行二分
那么二分是以一维数组为单位，分的是一维数组的区间从0-nm-1，每一次的mid的值转换成对应的二维数组的下标，进而和目标值进行比较。

算法1

时间复杂度为O(log n*n)=O(log n)

’‘’
class Solution {
public boolean searchMatrix(int[][] a, int target) {

    int lie=a[0].length;
    int hang=a.length;

    int l=0;
    int r=lie*hang-1;
    while(l<r){
        int mid=l+r+1>>1;
        if(a[mid/lie][mid%lie]>target) r=mid-1;
        else{
            l=mid;
        }

    }
    if(a[l/lie][l%lie]==target) return true;
    else{
        return false;
    }
}

}
‘’‘

题目2 题目连接 15. 二维数组中的查找

题目描述

同时还需要对数组是否为空做一个判断，在leetcode上的题目对数组的范围做了限定，保证数组一定不为0.
但是此题目没有规定需要加以判断

算法1

class Solution {

    public boolean searchArray(int[][] a, int target) {

       // System.out.println(lie +" "+hang);
        if(a==null || a.length==0 || (a.length==1 && a[0].length==0)) return false;
        int lie=a[0].length;
        int hang=a.length;
        int i=0;
        int j=lie-1;
        while(i<hang && j>=0){
            int x=a[i][j];
            if(x>target)j--;
            if(x<target)i++;
            if(x==target)return true;
        }
        return false;        

    }
}

算法2

算法2采用的时二分查找的方法，对行和列都进行一个二分查找
对上述两个题目都适用

class Solution {
    public static boolean  check(int h,int lie,int k,int a[][]) {
        int l=0;
        int r=lie;
        while(l<r){
            int mid=l+r>>1;

            if(a[h][mid] < k){
                l=mid+1;
            }else{
                r=mid;
            }
        }
        if(l<lie &&a[h][l]==k) return true;
        return false;


    }
    public boolean searchArray(int[][] a, int target) {

       // System.out.println(lie +" "+hang);
        if(a==null || a.length==0 || (a.length==1 && a[0].length==0)) return false;
          int lie=a[0].length;
        int hang=a.length;
        int l=0,r=hang;
        int k=target;
         while(l<r){
            int mid=l+r>>1;
            if(a[mid][0]<=k){
                //找到了
                if(check(mid, lie, k, a)){
                    return true;
                }
                else{
                    l=mid+1;
                }
            }else{
                r=mid;
            }
        }
        if( l>=0 && r<hang && check(l,lie,k,a)) return true;
        return false;

    }
}