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

public:
    bool Find(int target, vector<vector<int> > array) {
        if(array[0].size()==0)
            return false;
        // 暴力 遍历二位数组 逐个比对，超过要求的时间复杂度
        
        // 因为本来就是有序的 可以直接找 动态规划 每走一步 该点的左上角的矩阵 全都不符合要求
        int hang=array.size();
        int lie=array[0].size();
        
        // 从左下角开始
        int l=0,h=hang-1;
        // 每一个数字永远是他所在的左上角的矩阵中的最大值、
        // 那么只要是说 当前数字大于该点，则该点的左上角的矩阵都不符合要求 应该向右走
        // 如果说 该点 小了，那么所在的答案应该在该点向上一行的右上角
        
        // 用给的例子1289来说
        // 初始位置在最左下角6，如果数字是9
        // 9>6 那么6这一列 就都不可能是结果了
        // 向右走到8 同理 包含8的左上角的矩阵都不可能
        // 到11 大于9了，这说明 11右边的数字不可能是结果了，结果应该在11右上角的矩阵中 8 9/ 9 12/10 13 当中
        // 向上走到10 同理 只可能在10的右上角的矩阵中 8 9/9 12
        // 到了9，匹配正确，返回true
        
        // 假设不是9，答案是8.5
        // 8.5<9 向上 只可能在8 9中
        // 8.5>8 向右 只可能在9中
        // 8.5<9 向上 超出了数组的界限 所以返回false
        
        // 退出循环条件
        // 如果说 列超过了总共的列数，行小于0
        // 就说明不在二维数组中
        while(l<lie && h>=0){
            int num=array[h][l];
            // 如果相等 返回结果
            if(num == target)
                return true;
            // 不相等 要么太大 要么太小
            // 如果目标数字大于当前的数字 则向右走
            else if(num < target)
                l++;
            // 如果目标数字小于当前的数字 则向左走
            else if(num>target)
                h--;
        }
        return false;
    }
};