剑指 offer 笔记 01 | 二维数组中的查找

题目描述：

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

看着有点懵逼，不如在纸上先画出图形，先初始化一组数组，int [ 4 ] [ 4 ]，大概如下：

image.png

从题目要求可知道，要输入一个 target ，也就是目标数字，去二维数组中查找，是否存在，如果存在就返回 true ，不存在返回 false。

怎么查找呢？

大家有没有发现，这组二维数组的规律，每一行从左到右递增，每一列从上到下递增。

根据这个特点来查找，不知道大家有没有玩过“吃鸡”游戏，聪明的玩家喜欢边缘 OB ，在毒圈边界中活动。那么这个算法的核心也如此。

从每一行看，右上角的数字是该行的最大数字；

从每一列上看，右上角数字是该列的最小值；

关键点就是取数组右上角的数字，来与 target 比较；

如果第一行右上角的数字，刚好等于 target ，那么查找结束，返回 true；

如果 target 小于 数组右上角数字，那么这个右上角数字所在的列可以排除掉了（因为所在列是依次递增的）；

如果 target 大于 数组右上角数字，那么可以排除右上角数字所在行了；（原理同上）

就这样依次边缘 OB，缩小毒圈，成功吃鸡！

举个例子：

假设我现在要找的 target 是 7，要在二维数组中查询，第一次查询即如下：

image.png

第二次查询

image.png

第三次查询

image.png

核心代码如下：

public boolean Find(int target, int [][] array) {
if (array == null || array.length ==0 || array[0].length == 0) {
            return false;
        }
        int rows = array.length;//行数
        int columns = array[0].length;//列数
        if (target > array[rows - 1][columns - 1] || target < array[0][0]) {
            return false;
        }
        rows = 0;
        for (int i = columns - 1; i >= 0 && rows < array.length; ) {
            if (array[rows][i] == target) {
                return true;
            } 
            if (target < array[rows][i]) {
                i--;
                continue;
            } 
            if (target > array[rows][i]) {
                rows++;
                continue;
            }
        }
        return false;
    }

参考文献：
https://blog.csdn.net/u010002184/article/details/79518961
https://www.nowcoder.com/questionTerminal/abc3fe2ce8e146608e868a70efebf62e