剑指Offer-二维数组的查找

题目描述

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

解法

暴力法

思路：直接遍历数组，寻找二维数组中是否含有目标元素。（比较简单，这里就不多说了。）

时间复杂度为$O(m \times n)$
空间复杂度为$O(1)$

二分法

思路：题中的有序条件我们没有用上，而一看到有序数组，就应该想到二分查找🧐。对于一维数组的二分查找，设置左右指针，计算中间指针的位置，如果target大于中间指针对应的元素，则将左指针设置为当前中间指针位置；否则设置右指针。重复这个过程，直到查找到元素或左指针等于右指针停止循环。

而对于二维数组，我们不能简单的设置左右指针了，也不能简单的从一维扩展到二维。

例如上图，我们按照一维二分的思路，将中间元素指针定为[1, 1]，但此时如果target大于对应元素，中间指针将有右、下两个方向可以走；同样地，target小于对应元素，也会有左、上两个方向走。

所以我们可以利用右上方元素。

如果target大于array[0][3]，那么指针向下走；若小于，则指针向左走。这样就确定指针的唯一移动方向👍

public class Solution {
    public boolean Find(int target, int [][] array) {
        if (array == null || array.length == 0 || array[0].length == 0) return false;
        int row = array.length - 1;
        int column = array[0].length - 1;
        // 左上角元素
        int r = 0;
        int c = column;
        while (r <= row && c >= 0) {
            if (target > array[r][c]) r++;
            else if (target < array[r][c]) c--;
            else return true;
        }
        return false;
    }
}