二分与排序中等2 种解法

#74搜索二维矩阵

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

#数组#矩阵#二分查找

解题主线

矩阵按行展开后整体严格递增，虚拟下标 index 可映射到 matrix[index / columns][index % columns]。

也可以先在第一列找最后一个不大于 target 的行首，再在该行内二分。

文件名沿用了 Q240 前缀，但题意与实现实际对应 LeetCode 74。

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

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

时间复杂度

O(log(mn))

空间复杂度

O(1)

74. 搜索二维矩阵 · 虚拟一维数组二分

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;
    }
}

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

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

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

时间复杂度

O(log m + log n)

空间复杂度

O(1)

74. 搜索二维矩阵 · 定位行后行内二分

java

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

        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;
    }
}

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

边界与易错点

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

整理来源

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

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