Matrix Median

• Time : $O(nmlogm)$
• Space : $O(1)$

int nthElement(vector<vector<int>>& A, int k) {
    int n = A.size(), m = A[0].size();
    int l = INT_MAX, r = INT_MIN;
    for(auto row : A) {
        l = min(l, row.front());
        r = max(r, row.back());
    }
    
    int res = INT_MIN;
    
    while(l <= r) {
        int m = l + (r - l) / 2;
        int c = 0;
        for(auto row : A) {
            int p = lower_bound(begin(row), end(row), m) - begin(row);
            c += p;
        }
        if(c <= k) {
            l = m + 1;
            res = max(res, m);  
        } else r = m - 1;
    }
    
    return res;
}

int Solution::findMedian(vector<vector<int> > &A) {
    int n = A.size(), m = A[0].size();
    int all = n*m;
    if(all & 1) return nthElement(A,all / 2);
    return (nthElement(A,all / 2) + nthElement(A,all / 2 - 1)) / 2.;
}