搜索二维矩阵

题意

给定满足"每行递增、每行首元素大于上一行末元素"的 m x n 矩阵，判断 target 是否存在。要求 $O(\log(mn))$ 。

思路

矩阵的行间递增性质使得整行拼起来就是一个严格递增的一维数组。因此只需把一维下标 k 映射到二维：matrix[k / n][k % n]，然后对 k 做标准二分查找即可。

映射公式：k ∈ [0, m*n)，行号 k / n，列号 k % n。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32#include <bits/stdc++.h>
using namespace std;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, n, t;
    cin >> m >> n >> t;
    vector<vector<int>> a(m, vector<int>(n));
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];
    cout << Solution().searchMatrix(a, t) << '\n';
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28#!/usr/bin/env python3
from typing import List


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


def main():
    m, n, t = map(int, input().split())
    g = [list(map(int, input().split())) for _ in range(m)]
    print(Solution().searchMatrix(g, t))


if __name__ == "__main__":
    main()

复杂度

时间复杂度： $O(\log(mn))$ 。
空间复杂度： $O(1)$ 。

总结

二维矩阵的二分查找，核心是建立一维到二维的下标映射。前提是矩阵满足行间递增的严格条件，这样一维展开后仍有序。

目录

题意

思路

代码

复杂度

总结