矩阵二分查找：有序矩阵搜索

二维有序矩阵的查找题，和"第K小"问题，都能转化为二分来解决。

搜索二维矩阵（LeetCode 74）

矩阵按行从左到右升序，行尾 < 下一行行首（整体有序）。

思路：把矩阵视为一维有序数组，用 mid / cols、mid % cols 转换坐标。

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 val = matrix[mid / n][mid % n];
        if (val == target) return true;
        else if (val < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return false;
}

搜索二维矩阵 II（LeetCode 240）

每行从左到右升序，每列从上到下升序（但行尾 ≠ 下一行行首）。

思路：从右上角出发，相当于"二叉搜索树"。

public boolean searchMatrix(int[][] matrix, int target) {
    int row = 0, col = matrix[0].length - 1;
    while (row < matrix.length && col >= 0) {
        if (matrix[row][col] == target) return true;
        else if (matrix[row][col] > target) col--;
        else row++;
    }
    return false;
}

时间 O(m + n)，不是二分，但这个技巧很重要。

有序矩阵中第 K 小的元素（LeetCode 378）

矩阵行列均有序，找第 K 小的元素。

public int kthSmallest(int[][] matrix, int k) {
    int n = matrix.length;
    int lo = matrix[0][0], hi = matrix[n-1][n-1];
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        int count = countLessEqual(matrix, mid, n);
        if (count < k) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

// 统计 ≤ mid 的元素数量（从左下角出发）
private int countLessEqual(int[][] matrix, int mid, int n) {
    int count = 0, row = n - 1, col = 0;
    while (row >= 0 && col < n) {
        if (matrix[row][col] <= mid) { count += row + 1; col++; }
        else row--;
    }
    return count;
}

两个有序数组的中位数（LeetCode 4）

找两个有序数组合并后的中位数，要求 O(log(m+n))。

核心思路：二分分割，在较短的数组中找分割点，使左半部分的最大值 ≤ 右半部分的最小值。

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
    int m = nums1.length, n = nums2.length;
    int lo = 0, hi = m;
    while (lo <= hi) {
        int i = lo + (hi - lo) / 2;    // nums1 的分割点
        int j = (m + n + 1) / 2 - i;  // nums2 的分割点
        int maxLeft1  = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
        int minRight1 = (i == m) ? Integer.MAX_VALUE : nums1[i];
        int maxLeft2  = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
        int minRight2 = (j == n) ? Integer.MAX_VALUE : nums2[j];
        if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
            if ((m + n) % 2 == 1) return Math.max(maxLeft1, maxLeft2);
            return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0;
        } else if (maxLeft1 > minRight2) hi = i - 1;
        else lo = i + 1;
    }
    return 0;
}

总结