AC代码先上,注释是从看到题第一眼到AC所有的思考过程

底下有讲如何用二叉树理解这道题，毕竟这是一篇解题，就算重点讲二维数组也不能只说这一种理解

这是线性查找法，关于这种方法不会漏掉元素的证明：(这里证明用右上角，解题中用左下角）

可以证明这种方法不会错过目标值。如果当前元素大于目标值，说明当前元素的下边的所有元素都一定大于目标值，因此往下查找不可能找到目标值，往左查找可能找到目标值。如果当前元素小于目标值，说明当前元素的左边的所有元素都一定小于目标值，因此往左查找不可能找到目标值，往下查找可能找到目标值。

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.empty()||matrix[0].empty()) return false;
        int n=matrix.size();
        int m=matrix[0].size();
        //从左下角或右下角开始遍历，这里从左下角，
        //向右走j++，遇到大于则向上走，i--，再遇到小于则往右走j++，重复循环继续
        //右遇大上，上遇小右，右遇大再上
        //如果有一次转弯后遇到的第一个就又要转弯，则说明没有这个数返回false
        //用一个step变量判断，最外层是while循环,while里是俩for循环
        //如何进入for循环？要提前知道方向，用switchcase？算了还是if吧
        //应该把for循环的i和j位置变量定义在全函数
        //再给一个turn变量记录方向吧，为1是初始的向右，为0是向上
        //关于for循环的截止，这样想，多一个等于号，当恰好等于的时候也可以break出循环
        //while时候判断下当前位是否等于目标
        int i=n-1,j=0,turn=1;//从左下角出发开始遍历
        while(matrix[i][j]!=target&&i>=0&&j<=m-1){
            //step用的不好，考虑的不周全，去掉step，一路走到头吧
            if(turn==1){
                while(matrix[i][j]<target){
                    if(j<m-1) j++;
                    else return false;
                }
                turn=0;
            }else{
                while(matrix[i][j]>target){
                    if(i>0) i--;
                    else return false;
                }
                turn=1;
            }
        }
        if(matrix[i][j]!=target) return false;
        return true;
    }
};

我的用step的想法实在拉胯了，整个想法从头到尾就不对

想象一下5x5一步一拐，从左下角走到右上角，右上角满足条件，这step能用个屁，彻头彻尾的错误想法

二维数组讲解

先说二维数组在内存空间中的分配方式

对二维数组内存分配方式的理解对于求二维数组的长宽&总元素有很大的帮助

拿一个假设已经初始化完了未知元素数量的向量二维数组matrix做例子

vector<vecotr<int>> matrix;

首先明确容器类型是不能使用sizeof的，sizeof的返回值与数据个数，数据类型均无关，仅与编译器有关，记住就好

matrix.size()得到的是什么？

要先知道matrix是什么，由上面定义可以知道

matrix是一个元素类型为vector<int>的向量数组，也就是存在这里的，是vecotr<int>一维数组的地址，也是名字，也是这个一维数组的第一个元素

所以matrix.size()得到的是一维数组的个数

每个一维数组各自在内存中的分配是连续的，是二维数组的「一行」

一维数组的数组名在内存中的分配也是连续的，是二维数组的「第一列」

所以matrix.size()得到的就是二维数组的行数

那么matrix[0]由上面知道是一维数组的数组名

matrix[0].size()就是作为一行的一维数组的长度，也就是二维数组的列数

总结下

matrix.size()是二维数组的行数

matrix[0].size()是二维数组的列数

二叉树理解

把这个每列上到下递减，每行左到右递减的矩阵旋转45度，把左下角或者右上角当成根节点，则这个二叉树是二叉搜索树，每个节点的左分支更小，右分支更大

而往左右分支走到子节点后，如果结果存在，那么一定是在这个子节点的子节点...之中

不会再回头到父节点走另一分支了

这给了我们一种崭新的理解方式

其实这个搜索的过程就是不断地删除行和列，直到走到边界或者找到目标元素

还用从左下角往右上角线性查找的例子

在沿着列向上走的时候，因为从下到上递减，一旦在这列搜索中遇到比target小的了，那这个比target小的上面的其他元素，一定更加小，所以不用搜索了

直接删除这列，向右移动一列

由于从左到右递增，一旦遇到大于target的值，那这个值所在的这行的右侧的所有元素必然都要比target要大，所以也不用搜索

直接删除这行，向上移动一行

这是用二叉搜索树的理解去证明为什么线性查找法不会漏掉元素