240.搜索二维矩阵

思路一：二分查找

由于二维矩阵每行从左到右，和每列从上到下都是递增的。符合二分查找的条件。我们可以从第一行开始搜索目标值target,若搜不到则去搜索下一行，知道遍历完整个矩阵的行数。

// 二分查找
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
    // 这里需要带上引用，否则会超时
        for(auto &nums : matrix)
        {
            auto it = lower_bound(nums.begin(), nums.end(), target);
            if(it != nums.end() && *it == target)
                return true;
        }
        return false;
    }
};

lower_bound()函数： lower_bound() 函数用于在指定区域内查找不小于目标值的第一个元素。也就是说，使用该函数在指定范围内查找某个目标值时，最终查找到的不一定是和目标值相等的元素，还可能是比目标值大的元素。返回值是个迭代器。

思路二：单调性扫描 O(m+n)

从整个矩阵的右上角开始枚举，假设当前枚举的数是x:

• 如果x等于target，则说明我们找到了目标值，返回true；
• 如果x小于target, 则x左边的数一定都小于target,我们可以直接排除当前一整行的数；
• 如果x大于target，做x下边的数一定都大于target，我们可以直接排除当前一整列的数； 这个大佬讲的挺好的，直接放链接 搜索二维矩阵 II | 从右上角开始单调性扫描 | 代码简洁易懂 【c++/java版本】 - 搜索二维矩阵 II - 力扣（LeetCode） (leetcode-cn.com)