search2dMatrix

74. 搜索二维矩阵

分析

由于矩阵按行列有序，可以将整个二维矩阵视为一个长度为 n * m 的一维数组，并在这个一维数组上进行二分查找

矩阵映射为一维数组：
- 矩阵的第 i 行和第 j 列的元素 matrix[i][j]，在一维数组中对应的索引为 i * m + j
- 反之，一维数组的索引 k 对应矩阵中的元素为 matrix[k / m][k % m]
二分查找：
- 初始时，定义查找区间的左右端点为 l = 0 和 r = m * n - 1
- 每次取中点 mid，将其映射到二维矩阵元素 matrix[mid / m][mid % m] ，与 target 比较：
  - 若该值大于等于 target，收缩右边界 r = mid
  - 若该值小于 target，收缩左边界 l = mid + 1
- 循环结束时，检查索引 r 对应的矩阵元素是否等于 target

时间复杂度

每次二分查找都会将查找范围缩小为原来的一半，总体复杂度为 O(log(m * n))

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution
{
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target)
    {
        int n = matrix.size(), m = matrix[0].size(); // 矩阵行数和列数
        int l = 0, r = n * m - 1; // 二分区间 [l, r]
        while (l < r)
        {
            int mid = (l + r) >> 1; // 中点
            if (target <= matrix[mid / m][mid % m])
                r = mid; // 收缩右边界
            else
                l = mid + 1; // 收缩左边界
        }
        // 判断最终位置是否是目标值
        return matrix[r / m][r % m] == target;
    }
};