二分与排序中等2 种解法

#240搜索二维矩阵 II

在每行从左到右、每列从上到下都升序的矩阵中判断 target 是否存在。

#数组#矩阵#二分查找#分治

解题主线

每一行本身有序，可以独立二分；行之间的列序关系还可进一步利用。

右上角同时是所在行最大方向的端点和所在列最小方向的端点：值过大就左移，过小就下移。

阶梯搜索每一步排除一整行或一整列，因此最多移动 m + n 次。

解法 1：逐行二分查找

对每个有序行执行标准二分；任一行命中即返回。

时间复杂度

O(m log n)

空间复杂度

O(1)

240. 搜索二维矩阵 II · 逐行二分查找

java

final class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        for (int[] row : matrix) {
            int left = 0;
            int right = row.length - 1;
            while (left <= right) {
                int middle = left + (right - left) / 2;
                if (row[middle] == target) return true;
                if (row[middle] < target) left = middle + 1;
                else right = middle - 1;
            }
        }
        return false;
    }
}

对每个有序行执行标准二分；任一行命中即返回。

解法 2：右上角阶梯搜索

从右上角出发：当前值大于 target 就排除当前列并左移，小于 target 就排除当前行并下移。

时间复杂度

O(m + n)

空间复杂度

O(1)

240. 搜索二维矩阵 II · 右上角阶梯搜索

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 = 0;
        int column = matrix[0].length - 1;
        while (row < matrix.length && column >= 0) {
            int value = matrix[row][column];
            if (value == target) return true;
            if (value > target) column--;
            else row++;
        }
        return false;
    }
}

从右上角出发：当前值大于 target 就排除当前列并左移，小于 target 就排除当前行并下移。

边界与易错点

本题各行首元素不保证大于上一行尾元素，不能像第 74 题那样把矩阵整体拉平成有序数组。
旧文件两个逐行二分实现算法同构，整理后合并为一个。
读取 matrix[0] 前必须处理空矩阵。

整理来源

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

leetcode/src/main/java/medium/Q240_searchMatrixII.java