搜索二维矩阵 | 秋招知识库

由于矩阵的每一行是递增的，且每行的第一个数大于前一行的最后一个数，如果把矩阵每一行拼在一起，我们可以得到一个递增数组。

例如示例 1，三行拼在一起得

a = [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]

由于这是一个有序数组，我们可以用二分查找判断 $target$ 是否在 $matrix$ 中。

代码实现时，并不需要真的拼成一个长为 $m n$ 的数组 $a$ ，而是将 $a [i]$ 转换成矩阵中的行号和列号。例如示例 1， $i = 9$ 对应的 $a [i] = 30$ ，由于矩阵有 $n = 4$ 列，所以 $a [i]$ 在 $⌊ \frac{i}{n} ⌋ = 2$ 行，在 $i mod n = 1$ 列。

一般地，有

a [i] = matrix [⌊ i / n ⌋] [i mod n]

关于二分查找的原理，请看视频讲解：二分查找红蓝染色法【基础算法精讲 04】

下面用的开区间二分，其它写法也可以。

Python 解法1C++ 解法1

python

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        left, right = -1, m * n
        while left + 1 < right:
            mid = (left + right) // 2
            x = matrix[mid // n][mid % n]
            if x == target:
                return True
            if x < target:
                left = mid
            else:
                right = mid
        return False

cpp

// C++ 版待补充

Python 解法2C++ 解法2

python

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        # 注：range 不是 list，是一个对象，创建 range 和下标访问都是 O(1) 的
        i = bisect_left(range(m * n), target, key=lambda i: matrix[i // n][i % n])
        return i < m * n and matrix[i // n][i % n] == target

cpp

// C++ 版待补充

C++ 解法3

cpp

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int left = -1, right = m * n;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            int x = matrix[mid / n][mid % n];
            if (x == target) {
                return true;
            }
            (x < target ? left : right) = mid;
        }
        return false;
    }
};