74. 搜索二维矩阵

难度：🟡 Medium | 标签：二分查找、矩阵 | 状态：⬜ LeetCode 链接

思路

矩阵按行展开是有序的（每行升序、行尾 < 下一行行首）。 当作一维数组二分，下标 mid 对应 (mid/C, mid%C)。

代码

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& m, int target) {
        int R = m.size(), C = m[0].size();
        int l = 0, r = R * C;
        while (l < r) {
            int mid = l + (r - l) / 2;
            int v = m[mid / C][mid % C];
            if (v == target) return true;
            if (v < target) l = mid + 1;
            else r = mid;
        }
        return false;
    }
};

复杂度

• 时间 O(log(R · C))，空间 O(1)

易错 / 回顾

• 与 240 的区别：本题严格全局有序，可一次二分；240 只行 / 列内部有序，要 Z 字搜索
• 二维 → 一维下标映射：(i, j) ↔ i * C + j