LeetCode刷题记录----74.搜索二维矩阵（Medium）

2025/9/1

题目（Medium）：

我的思路：

变回一维数组，然后按一维数组的方式来进行二分查找。

我们知道，如果一个矩阵的长宽分别是m,n，那它对应的一维数组的长度就是m*n。因此我们可以获取它对应的一维数组索引的首位位置分别是0，m*n-1。而我们每次得到mid之后因为需要去矩阵中获取相应的值，因此需要把mid转化为相应的行列索引。至于怎么转化呢?

行索引：row = mid / n

列索引：colum = mid % n

即分别用行数对mid分别进行除以和取模即可得到行列索引值。

至于其他部分和普通的二分查找一样了就

具体代码如下：
 

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int left = 0, right = m * n -1;

        while(left <= right){
            int mid = (left + right) / 2;
            int row = mid/n;
            int column = mid%n;
            if(matrix[row][column] == target){
                return true;
            }
            else if(matrix[row][column] > target){
                right = mid - 1;
            }
            else if(matrix[row][column] < target){
                left = mid + 1;
            }
        }

        return false;
    }
};

时间复杂度：O（logmn)【相当于在长度为m*n的一维数组中查找的时间复杂度】

空间复杂度：O（1）

优化思路：

还可以利用矩阵的特性，先对定位到对应的行，再在这一行中进行二分查找

对于定位到具体的行，我们可以用std库中的函数upper_bound(开始，结尾，目标值，比较函数)来实现

对于在具体的行中进行二分查找，我们可以直接用binary_search(开始，结尾，目标值)方法来简化

具体代码如下：

class Solution {
public:
    bool searchMatrix(vector<vector<int>> matrix, int target) {
        //利用矩阵的特性通过行列查找
        //先查找目标行
        auto row = upper_bound(matrix.begin(), matrix.end(), target, [](const int target, const vector<int>& rowArray){
            return target < rowArray[0];
        });
        //如果连第一行的首元素都比他大， 那他肯定不在矩阵里了
        if(row == matrix.begin()){
            return false;
        }

        //回到实际的行位置
        row--;

        //然后在这一行中进行二分查找
        return binary_search(row -> begin(), row -> end(), target);
    }
};

时间复杂度：O（logm + logn)【upper_bound中进行的也是二分查找的】【logm + logn = logmn】

空间复杂度：O（1）

总结：

①对于矩阵中二分查找，我们可以把他转化成在一维数组中查找的思路进行搜索。

②还可以利用矩阵的特性先对行进行二分查找定位，再在这一行中进行二分查找

③upper_bound和binary_search是C++中帮我们写好的方法，可以直接拿来用。一个用于自定义比较规则的二分查找，一个是进行真的二分查找

④C++中lambda表达式的写法是[](){}