题解 | #二维数组中的查找#

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int rowMax=array.size()-1;
        if(rowMax==-1)
            return false;
        int colMax=array[0].size()-1;
        if(colMax==-1)
            return false;

        //定义（i，j）指针
        int i=0,j=colMax;//从二叉树的根结点开始
        while(i<=rowMax&&j<=colMax&&i>=0&&j>=0)
        {
            
            if(array[i][j]==target)
            {
                return true;
            }
            else if(array[i][j]<target)//如果大于根结点
            {
                ++i;//转移到右子树
            }
            else 
            {
                --j;//小于遍历左子树
            }
        }

        return false;
        
    }
};

将数表逆时针旋转45度，发现数表类似于一颗二分排序树，每走过一个结点，将排除未走过的另一棵子树的根结点，这样遍历的结点每次只有两个方向可走：

若target大，走右子树，target小走左子树，不会逆遍历子树（因为正在判断的结点的直接双亲结点已经在上一个结点判断时排除了），这就保证了在线性复杂度内找到target结点（或者遍历出子树）