搜索二维矩阵 图解题解

这道题给的矩阵，行和行之间有什么讲究

给一个 m 行 n 列的矩阵，每行升序，且下一行第一个数比上一行最后一个数大。判断 target 在不在里面，要做到 O(log(m·n))。约定用（行号,列号）定位格子、都从 0 数起。题面 6 行 7 列，target=104 得 true，target=87 落在 86 和 89 之间、表里没有，得 false。

逐个格子比一遍、或者逐行二分，为什么都不够快

42 个格子逐个比最坏 42 次，即 O(m·n)，顶不住 O(log(m·n)) 的线。退一步对每行各二分，O(m·log n)，外层仍逐行走 m 趟。题目要把 m 也塞进 log，这两种都差一口气。

为什么整张矩阵能当成一条排好序的长队

关键在那条行间约束：每行内部升序，下一行开头又比上一行结尾大，把每行首尾接起来，整张矩阵就是一条完全升序、中间不回头变小的序列。既然有序，就不必管它折成几行——拉直成一维（下标 0 到 m·n-1）当成有序数组，直接二分即可。

下标砍到中间那格，怎么换回它在第几行第几列

起手 lo=0、hi=m·n-1 两个一维下标，罩住全部 42 个数。每轮取中点 mid（正中间那个下标，mid=(lo+hi)//2），把这下标还原回二维：行 = mid÷n（整除），列 = mid%n（取余），值是 matrix[mid÷n][mid%n]。拿它和 target 比，三种走向：等于就找到；比 target 大就丢右半，hi 收到 mid-1；比它小就丢左半，lo 进到 mid+1。

两个 target 各走一轮 lo、mid、hi

题面这张表 6 行 7 列（下标从 0 起），一维下标换回二维按列数 7 分组：÷7 得行、%7 得列。先找 104：lo=0、hi=41，mid=20 是 matrix[2][6]=62<104，lo 到 21；mid=31 是 matrix[4][3]=95<104，lo 到 32；mid=36 是 matrix[5][1]=110>104，hi 收到 35；mid=33 是 matrix[4][5]=101<104，lo 到 34；mid=34 是 matrix[4][6]=104，命中，返回 true。

再找 87：mid=20 的 62<87，lo 到 21；mid=31 的 95>87，hi 到 30；mid=25 是 matrix[3][4]=77<87，lo 到 26；mid=28 是 matrix[4][0]=86<87，lo 到 29；mid=29 是 matrix[4][1]=89>87，hi 到 28。此时 lo=29 超过 hi=28，范围空了，返回 false。

换算行列时除数用错，满盘跟着挪位

还原下标按列数 n 分组：行用 mid÷n、列用 mid%n。把 n 错写成行数 m，行列全乱，取到的不是那格。时间 O(log(m·n))，每轮范围减半；空间 O(1)，只用几个下标。循环条件要带等号写 lo<=hi，否则 lo、hi 撞到同一格便不再检查、那格恰是 target 就漏掉；范围大时用 lo+(hi-lo)÷2 防 mid 溢出。

Python

def searchMatrix(matrix, target):
    m, n = len(matrix), len(matrix[0])
    lo, hi = 0, m * n - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        v = matrix[mid // n][mid % n]   # 下标还原成行列
        if v == target:
            return True
        elif v > target:
            hi = mid - 1               # 丢右半
        else:
            lo = mid + 1               # 丢左半
    return False

C++

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int lo = 0, hi = m * n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int v = matrix[mid / n][mid % n];   // 下标还原行列
            if (v == target) return true;
            else if (v > target) hi = mid - 1;  // 丢右半
            else lo = mid + 1;                  // 丢左半
        }
        return false;
    }
};

Java

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int lo = 0, hi = m * n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int v = matrix[mid / n][mid % n];   // 下标还原行列
            if (v == target) return true;
            else if (v > target) hi = mid - 1;  // 丢右半
            else lo = mid + 1;                  // 丢左半
        }
        return false;
    }
}