数组--二维数组中的查找

题目描述

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

样例
输入数组：
[1,2,8,9]，
[2,4,9,12]，
[4,7,10,13]，
[6,8,11,15]
如果输入查找数值为7，则返回true，
如果输入查找数值为5，则返回false。

代码格式要求

public class Solution {
    public boolean Find(int target, int [][] array) {
    }
}

解题

一、暴力法

思路-直接遍历数组

public class Solution {
    public boolean Find(int target, int [][] array) {
        for(int i=0;i<array.length;i++){      //array.length表示数组的行数
           for(int j=0;j<array[0].length;j++){    //array[0].length表示数组指定行的列数
               if(array[i][j]==target){
                   return true;
               }
           }
       }
        return false;
    }
 //  测试
     public static void main(String[] args){
         Solution a=new Solution();
         int b[][]={ { 1, 2, 4, 5 }, { 3, 4, 9, 12 }, { 4, 8, 10, 13 }, { 6, 14, 15, 16 } };
         boolean x=a.Find(8,b);     
         System.out.println("x:"+x);
     }
}

复杂度
时间复杂度：O(n^2)
空间复杂度：O(1)

二、右上角法

1.思路
首先选取数组中右上角的数字。如果该数字等于要查找的数字，查找过程结束；如果该数字大于要查找的数组，剔除这个数字所在的列；如果该数字小于要查找的数字，剔除这个数字所在的行。也就是说如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围中剔除一行或者一列，这样每一步都可以缩小查找的范围，直到找到要查找的数字，或者查找范围为空。

2、举例
过程如下：

image.png
image.png
image.png

3.代码

public class Solution {
  public boolean Find(int target, int [][] array) {
      //判断边界条件
      if(array==null||array[0]==null||array.length==0||array[0].length==0)   
      return false;
      //获取矩阵的行数m，列数n
      int m=array.length,n=array[0].length;
      //初始化一开始元素的位置（这里设置右上角）
      int i=0,j=n-1;
      //循环遍历整个函数
      while(i<m&&j>=0) {
          if(target>array[i][j])  //如果目标值大于右上角的数字消去第一行i++
              i++;
          else if(target<array[i][j]) //如果目标值小于右上角的数字消去最后一列j--
              j--;
          else return true;  //如果相等返回true
      }
      return false;    
  }
  
   public static void main(String[] args){
       Solution mm=new Solution();
       int a[][]={ { 1, 2, 4, 5 }, { 3, 4, 9, 12 }, { 4, 8, 10, 13 }, { 6, 14, 15, 16 } };
       boolean x=mm.Find(8,a);        
       System.out.println("x:"+x);
   }
}

4.复杂度分析
时间复杂度：O(n+m) 。在循环语句中，除非直接返回结果，否则每一次行都会递减一次或者列都会递增一次。该矩阵共有 m 行 n 列，因此循环终止之前，循环不会运行超过 n+m 次。其它的操作都是常数，所以总的时间复杂度是线性的。
空间复杂度：O(1)。没有使用额外的存储空间，所以它的内存占用是恒定的。

三、二分查找

二分查找的条件是对一组有序数组的查找；在使用二分查找的时候先要对数组进行排序。
1.思路
思路：一个有序数组，想要查找一个数字key的下标，首先算出中间下标mid，利用mid把这个数组分为两半，前一半从下标0到mid-1，后一半从mid+1到数组最后一个元素（下标是数组长度减一）。把这个查找的元素key和数组下标为mid的元素进行比较，也就是和中间那个元素进行比较，如果比这个元素的小那么把查找范围缩小到原数组的前一半（把查找下标缩短到0到mid-1），如果比中间mid下标元素大那么范围就是后半部分（下标为mid+1到数组长度减一），这样来回反复取中间比较最后就会定位到要查找元素key的下标。
2.代码

 public boolean Find(int target, int [][] array)
             {//判断边界条件
                 if(array==null||array[0]==null||array.length==0||array[0].length==0) 
                 return false;
                 //循环遍历整个函数
                 for(int i=0;i<array.length;i++)
                 { //获取矩阵下标的最小值low，最大值为high
                     int low=0,high=array[i].length-1;
                     while(low<=high) 
                        {int mid=(low+high)/2;
                     if (target<array[i][mid])
                         high=mid-1;                 
                     else if(target>array[i][mid])
                         low=mid+1;     
                     else 
                        return true;
                        }
                   }
                 return false;  
            }