Getting wrong answer in Binary Search solution

Question

Problem statement

You are given a row-wise sorted matrix mat of size m * n where m and n are the numbers of rows and columns of the matrix, respectively.

Your task is to find and return the median of the matrix.

Note: m and n will always be odd.

Example:

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

Explanation: If we arrange the elements of the matrix in the sorted order in an array, they will be like this

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 

So the median is 10, which is at index 12, which is midway as the total elements are 25, so the 12th index is exactly midway. Therefore, the answer will be 10.

This is the question I am trying to solve using Binary Search. Below is the code I have written but it is only able to pass some test cases and showing wrong answer in other cases. I am unable to find if I have made some logical error or my code doesn't work on edge cases.

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

I have used the optimal solution to solve this problem using Binary Search and Upper Bound. Finding the range of the search space then appying Binary Search on it. However, I am not able to pass all the test cases. The difference is only of 1 between my answer and the correct answer.

Answer 1

import java.util.Arrays;

public final class Solution {

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

}