描述

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

[

  [1,2,8,9],
  [2,4,9,12],
  [4,7,10,13],
  [6,8,11,15]

]

给定 target = 7，返回 true。

给定 target = 3，返回 false。

示例1

输入：

7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

返回值：

true

说明：

存在7，返回true

示例2

输入：

3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

返回值：

false

说明：

不存在3，返回false

解题思路

知识复习：

二维数组可以看做是一个特殊的一维数组。

怎么特殊呢，就相当于每一个元素都是一个一维数组。可以参照下图发挥想象力

所以，array[0].length代表列数。

          array.length代表行数。

下面开始我的分析：

法一：当然了，最简单的方法就是暴力遍历，如果找到了，直接return

           脑子不太转想不出来方法的小菜鸟，就最喜欢这种方法啦~（比如我。。。）

代码

public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array.length==0 || array==null){
            return false;
        }
        for(int i=0; i < array.length; i++){
            for(int j=0; j<array[0].length;j++){
                if(array[i][j]==target){
                    return true;
                }
            }
        }
       return false; 
    }
}

法二：大家可以看我标黄色的半圈：

           从左到右，就是从小到大；

           右上角的数字就是标黄部分的中位数。

          所以可以变相的采用二分思想

步骤1：从右上角开始，首先选右上角的数字，如果它等于要查找的数字，则查找过程结束。

步骤2：如果要查找的数字大于右上角数字，删除右上角数字所在行，因为要查找的数字在右上角数字所在列

步骤3：如果要查找的数字小于右上角的数字，删除右上角数字所在列，以为要查找的数字在右上角数字所在行

代码

public class Solution {
    public boolean Find(int target, int[][] array) {
        if(array == null || array.length == 0 || array[0].length==0){
            return false;
        }
        int is = array.length;
        int js = array[0].length;

        //从右上角的数字开始 
        int i = 0;
        int j = js - 1;

        while(i <is && j >= 0){
            if(array[i][j] == target){
                return true;
            }else if(array[i][j] > target){
                j--;
            }else{
                i++;
            }
        }
          return false; //矩阵遍历完没有找到，返回false
    }
}

 还有其他方法欢迎补充，我的小脑瓜最喜欢这两种方法啦嘿嘿~