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

1. 暴力法

直接遍历二维数组，如果存在就返回true。时间复杂度O(n2)。

 //暴力法
    public boolean Find1(int target, int[][] array) {
        for (int[] arr : array) {
            for (int a : arr) {
                if (target == a) {
                    return true;
                }
            }
        }
        return false;
    }

测试结果：

运行时间：181ms 占用内存：17444k

2. 从左下角查找

由于序列具有以下性质：

  • 一行都按照从左到右递增的顺序排序
  • 每一列都按照从上到下递增的顺序排序

对左下角m来说，是该列最大值，是该行最小值

  1. 若m==target，返回true
  2. 若m>target，则row–
  3. 若m<target，则col++

时间复杂度为：O(rows+cols)

 //从左下角比较
    public boolean Find2(int target,int[][] array){
            int rows=array.length;
            if(rows==0)return  false;
            int cols=array[0].length;
            int row=rows-1;
            int col=0;
            while(row>=0&&col<cols){
                if(array[row][col]>target)row--;
                else if(array[row][col]<target)col++;
                else return true;
            }
            return false;
    }

测试结果：

运行时间：165ms 占用内存：18488k

3.折半查找

从最后一行向上比较确定在那一行，对此行使用折半查找。对m行n列矩阵数组，时间复杂度为O(m+log2n)

 public boolean Find3(int target,int[][] array) {
        int rows=array.length;
        System.out.println(rows);
        if(rows==0)return false;
        int cols=array[0].length;
        if(cols==0)return  false;
        for(int row=rows-1;row>=0;row--){
            if(target>=array[row][0]&&target<=array[row][cols-1]){
                if(array[row][0]==target)return true;
                if(array[row][cols-1]==target)return true;
                int left=0,right=cols-1;
                while (left<right){
                    int mid=left+(right-left)/2;
                    if(array[row][mid]==target)return true;
                    if(array[row][mid]>target)right=mid-1;
                    if(array[row][mid]<target)left=mid+1;
                }
                break;          //查找终止
            }
        }
        return false;
    }

测试结果：

运行时间：146ms 占用内存：18064k