A matrix with an odd number of rows and columns, each row sorted — find the median.
Brute force: flatten to a 1D array, sort, take the middle — O(nm + nm·log(nm)).
Optimal — binary search on value, not position: the search space is [min(matrix), max(matrix)].
For a candidate mid, count how many elements are <= mid across all rows using the
upper-bound technique per row; if that count is <= (m*n)/2, the
median must be larger (eliminate the left half), otherwise mid could be the median or too large
(eliminate the right half).
The steps: find min(matrix) and max(matrix) (from the first and last columns, since rows are
sorted), place low/high there, compute mid, sum upperBound(row, mid) across every row to
get smallEqual. If smallEqual <= (M*N)/2, the median is bigger — eliminate the smaller half
(low = mid+1). Otherwise, mid might be the median but a smaller one might also work —
eliminate the right half (high = mid-1). Continue until low crosses high.