二分与排序中等2 种解法

#74搜索二维矩阵

在每行递增且下一行首元素大于上一行尾元素的矩阵中判断 target 是否存在。

#数组#矩阵#二分查找

原题

给你一个满足下述两条属性的 m x n 整数矩阵：

每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

你必须编写一个时间复杂度为 O(log(m * n)) 的解决方案。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10⁴ <= matrix[i][j], target <= 10⁴

查看原题

解题主线

矩阵按行展开后整体严格递增，虚拟下标 index 可映射到 matrix[index / columns][index % columns]。
也可以先在第一列找最后一个不大于 target 的行首，再在该行内二分。
文件名沿用了 Q240 前缀，但题意与实现实际对应 LeetCode 74。

解法 1：虚拟一维数组二分

不实际复制矩阵，通过除法和取模把一维中点映射回行列，在 [0, m × n - 1] 上二分。

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

JAVA

final class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int columns = matrix[0].length;
        // 将矩阵视为一个整体递增的一维数组，避免额外复制。
        int left = 0;
        int right = matrix.length * columns - 1;
        while (left <= right) {
            int middle = left + (right - left) / 2;
            // 商映射到行，余数映射到列。
            int value = matrix[middle / columns][middle % columns];
            if (value == target) return true;
            if (value < target) left = middle + 1;
            else right = middle - 1;
        }
        return false;
    }
}

解法 2：定位行后行内二分

先二分第一列，找到行首不超过 target 的最后一行，再在该行执行标准二分。

时间复杂度： O(log m + log n)
空间复杂度： O(1)

JAVA

final class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        // 先找最后一个行首不大于 target 的候选行。
        int row = candidateRow(matrix, target);
        if (row < 0) return false;

        // 候选行内保持递增，再执行一次标准二分。
        int left = 0;
        int right = matrix[row].length - 1;
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (matrix[row][middle] == target) return true;
            if (matrix[row][middle] < target) left = middle + 1;
            else right = middle - 1;
        }
        return false;
    }

    private int candidateRow(int[][] matrix, int target) {
        int left = -1;
        int right = matrix.length - 1;
        while (left < right) {
            int middle = left + (right - left + 1) / 2;
            if (matrix[middle][0] <= target) left = middle;
            else right = middle - 1;
        }
        return left;
    }
}

边界与易错点

不要把本题与第 240 题混淆；只有本题保证跨行也保持整体有序。
两阶段二分的第一步可能得到 -1，表示 target 小于第一行首元素。
计算虚拟下标上界前需确认矩阵非空。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/medium/Q240_searchMatrixI_Q74.java