剑指offer：二维数组中的查找

前言

牛客网剑指offer的66道题，刷起来！每道题会提供简单的思路以及测试通过的代码

题目描述

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
注：点击左下角的阅读原文可以直达原文提交你的代码

解答思路

一种简单的方法就是整个数组都遍历，当然，数组从左到右，从上到下都是有序的，如果你遍历整个数组的话，那就浪费了数组的局部有序性了。

如果我们从 row = 0 和col = 0开始遍历的话，发现右边的数比 array[row][col] 大，而下边也比 array[row][col]大，这样的话，貌似局部有序性没有派上用场。

遍历不一定要从 row = 0 和 col = 0开始，有时候，换个角度，一切就豁然开朗了。实际上我们从数组的左下角开始遍历的话，如果 array[row][col] > target，则往上移动，如果array[row][col] < target，则往右移动，否则找到目的数。这样，就完美利用到局部有序性了。代码如下：

 1    public boolean Find(int target, int [][] array) {
 2        if(array == null)return false;
 3        int row = array.length - 1;
 4        int col = array[0].length - 1;
 5        int j = 0;
 6        while (row >= 0 && j <= col) {
 7            if (array[row][j] > target) {
 8                row--;
 9            } else if (array[row][j] < target) {
10                j++;
11            } else {
12                return true;
13            }
14        }
15        return false;
16    }

往期

关注我，每天进步一点点