在二分查找解决方案中得到错误答案

Question

问题陈述

给定一个按行排序的矩阵

mat

，大小为

m * n

，其中

m

和

n

分别是矩阵的行数和列数。

您的任务是找到并返回矩阵的中值。

注意：

m

和

n

始终为奇数。

示例：

Input: n = 5, m = 5
mat = [     
        [ 1, 5, 7, 9, 11 ],
        [ 2, 3, 4, 8, 9 ],
        [ 4, 11, 14, 19, 20 ],
        [ 6, 10, 22, 99, 100 ],
        [ 7, 15, 17, 24, 28 ]   
      ]

Output: 10

说明：如果我们将矩阵的元素按排序顺序排列在数组中，它们将是这样的

1 2 3 4 4 5 6 7 7 8 9 9 10 11 11 14 15 17 19 20 22 24 28 99 100 

所以中位数是

10

，位于索引

12

处，由于总元素为

25

，所以它位于中间，所以第12个索引正好位于中间。因此，答案将是

10

。

这是我试图使用二分搜索解决的问题。下面是我编写的代码，但它只能通过一些测试用例，并在其他情况下显示错误的答案。我无法确定我是否犯了一些逻辑错误或者我的代码在边缘情况下不起作用。

import java.util.Arrays;

public final class Solution {
    public static int findMedian(int matrix[][], int m, int n) {
        // Write your code here
        int[] pos= findPos(matrix,m,n);
        int req=(m*n)/2;
        while (pos[0]<=pos[1]) {
            int mid = (pos[0]+pos[1])/2;
            int smallEquals = blackbox(matrix,m,n,mid);
            if(smallEquals>=req){
                pos[1]=mid-1;
            }else{
                pos[0]=mid+1;
            }
        }
        return pos[0];
    }
    public static int blackbox(int matrix[][], int m, int n, int mid){
        int cnt=0;
        for (int i = 0; i < m; i++) {
            int low=0;
            int high=n-1;
            while(low<=high){
                int mid1=(low+high)/2;
                if(matrix[i][mid1]<mid){
                    low=mid1+1;
                }else{
                    high=mid1-1;
                }
            }
            cnt+=low;
        }
        return cnt;
    }
    public static int[] findPos(int matrix[][], int m, int n){
        int min=matrix[m-1][n-1];
        int max=matrix[0][0];
        for(int i=0; i<m; i++){
            if(matrix[i][0]<min){
                min=matrix[i][0];
            }
            if(matrix[i][n-1]>max){
                max=matrix[i][n-1];
            }
        }
        return new int[]{min,max};
    }
}

我已经使用二分搜索和上限来解决这个问题的最佳解决方案。找到搜索空间的范围，然后对其应用二分搜索。但是，我无法通过所有测试用例。我的答案和正确答案之间只有 1 的差别。

Answer 1

导入java.util.Arrays；

公开期末课解决方案{

public static int findMedian(int[][] matrix, int m, int n) {
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            min = Math.min(min, matrix[i][j]);
            max = Math.max(max, matrix[i][j]);
        }
    }

    int left = 0;
    int right = m * n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (countSmallerThan(matrix, m, n, mid) >= (m * n + 1) / 2) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return left;
}

private static int countSmallerThan(int[][] matrix, int m, int n, int value) {
    int count = 0;
    for (int i = 0; i < m; i++) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (matrix[i][mid] < value) {
                count += (high - mid) + 1;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
    }
    return count;
}

}