方法一

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for(auto row : matrix){
            auto it = lower_bound(row.begin(),row.end(),target);
            if(it !=row.end() && *it==target){
                return true;
            }
        }
        return false;
    }
};

这段代码的核心就是：逐行二分查找 target。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for (const auto& row : matrix) {
            auto it = lower_bound(row.begin(), row.end(), target);

            if (it != row.end() && *it == target) {
                return true;
            }
        }
        return false;
    }
};

关键知识记住这几个：

lower_bound(row.begin(), row.end(), target)：在有序行中找到第一个 >= target 的位置。

it：表示位置；*it：表示这个位置上的值。

row.begin()：第一个元素的位置；row.end()：最后一个元素的后一个位置。

if (it != row.end() && *it == target)

要先判断 it 没有到 end()，才能安全使用 *it。

const auto& row

表示直接读取矩阵中的一行，不复制，也不修改。

复杂度：如果有 m 行、n 列，每行二分是 O(log n)，所以总时间复杂度：

\[ \boxed{O(m\log n)} \]

一句话记忆：

遍历每一行 → lower_bound 二分查找 → 找到且值等于 target 就返回 true。

方法二

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(),n=matrix[0].size();
        int x = 0,y=n-1;
        while(x<m && y>=0){
            if(matrix[x][y]==target){
                return true;
            }
            if(matrix[x][y]>target){
                y--;
            }
            else{
                x++;
            }
        }
        return false;
    }
};

这个方法比“每行二分”更巧，核心是：从右上角开始找。

int x = 0, y = n - 1;

表示起点在右上角。

比如矩阵：

1   4   7   11
2   5   8   12
3   6   9   16

起点是 11。

为什么选右上角？因为这里有一个特点：

• 往左走，数字变小
• 往下走，数字变大

所以每比较一次，都能排除一整行或一整列。

假设：

target = 5;

开始：

1   4   7  [11]
2   5   8   12
3   6   9   16

11 > 5，说明当前这一列下面的数只会更大，所以 11 这一列当前位置不可能有答案，直接：

--y;

向左走到 7。

1   4  [7]  11
2   5   8   12
3   6   9   16

7 > 5，继续向左：

1  [4]  7   11
2   5   8   12
3   6   9   16

现在 4 < 5。

因为这一行左边的数字只会比 4 更小，所以当前这一行不可能找到 5，于是：

++x;

向下走：

1   4   7   11
2  [5]  8   12
3   6   9   16

找到：

matrix[x][y] == target

返回：

true;

所以这三种情况直接记：

if(matrix[x][y] == target)
    return true;

if(matrix[x][y] > target)
    --y;   // 太大，向左

else
    ++x;   // 太小，向下

循环条件：

while (x < m && y >= 0)

表示只要还没有走出矩阵，就继续寻找。

整个移动路线只有：

← ← ←
    ↓
    ↓

最多向左走 n 次，向下走 m 次，所以时间复杂度：

\[ \boxed{O(m+n)} \]

空间复杂度：

\[ \boxed{O(1)} \]

一句话记忆：

右上角开始：当前值大了就向左，小了就向下。

这个方法成立的前提是：每一行从左到右递增，每一列从上到下递增。