Median in a row sorted matrix

#include <bits/stdc++.h>
using namespace std;

class Solution{   
public:
    // Function to count elements <= mid_val using binary search
    int countSmallerThanOrEqualToMid(vector<int> &row, int mid_val) {
        int low = 0, high = row.size() - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (row[mid] <= mid_val) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return low;  // The number of elements <= mid_val
    }

    int median(vector<vector<int>> &matrix, int R, int C){
        int min_val = INT_MAX;
        int max_val = INT_MIN;

        // Find the minimum and maximum element in the matrix
        for (int i = 0; i < R; ++i) {
            if (matrix[i][0] < min_val) min_val = matrix[i][0];
            if (matrix[i][C - 1] > max_val) max_val = matrix[i][C - 1];
        }

        int desired_count = (R * C + 1) / 2;
        
        while (min_val < max_val) {
            int mid_val = min_val + (max_val - min_val) / 2;
            int count = 0;

            // Count elements <= mid_val using binary search
            for (int i = 0; i < R; ++i) {
                count += countSmallerThanOrEqualToMid(matrix[i], mid_val);
            }

            // Adjust search range based on the count
            if (count < desired_count) {
                min_val = mid_val + 1;
            } else {
                max_val = mid_val;
            }
        }
        
        return min_val;
    }
};

int main() {
    int t;
    cin >> t;
    while (t--) {
        int r, c;
        cin >> r >> c;
        vector<vector<int>> matrix(r, vector<int>(c));
        for (int i = 0; i < r; ++i)
            for (int j = 0; j < c; ++j)
                cin >> matrix[i][j];
        Solution obj;
        int ans = obj.median(matrix, r, c);
        cout << ans << "\n";        
    }
    return 0;
}