一 题目描述

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

二 思路及解题

1. 暴力穷举：将targer与数组元素逐一进行比对
   复杂度：O(n*n)

public class Solution {
  public boolean Find(int target, int [][] array) {
      // 获取二维数组的行长和列长
      int row_len = array.length;
      int col_len = array[0].length;
      //数组为空，返回false
      if(row_len == 0){
          return false;
      }
      if(col_len == 0){
          return false;
      }
      
      // 将数组中元素逐个与 `target`进行比较 
      for(int i = 0 ; i<row_len ;i++){
          for(int j = 0;j< col_len;j++){
              if(array[i][j] == target){
                  return true;
              }
          }
      }
      return false;
  }
}

1. 逐行进行二分查找
   复杂度：O(n*logn)

public class Solution {
    public boolean Find(int target, int [][] array) {
        // 获取二维数组行列
        int row_len = array.length;
        int col_len = array[0].length;
        //数组为空，返回false
        if(row_len == 0){
            return false;
        }
        if(col_len == 0){
            return false;
        }
       for(int i=0 ; i<col_len ; i++){
           int low = 0;
           int high = row_len - 1;
           int mid = (low+high)/2;
           while(low<=high){
               if(target<array[i][mid]){
                   high = mid-1;
               }else if(target > array[i][mid]){
                   low = mid + 1; 
               }else
                   return true;
               mid = (low+high)/2;
           }
           
       }
        return false;
    }
}

参考社会王哥代码