Baseline Binary Search · 2D Arrays O(R * log C * log(max - min)) · O(1)
A power monitor banks its readings row by row, each bank kept in ascending order, and the control room needs the median of every reading combined. Flattening all banks would blow the memory budget on large grids, so the median is hunted in the value domain: binary search a candidate value and count how many readings sit at or below it.
Input: An R x C matrix of integers, row-wise sorted, where R and C are both odd.
Output: The median of the R * C values in the matrix (the middle element of the sorted combination).
1 <= R, C <= 200 (both odd in the canonical judge)1 <= matrix[i][j] <= 2000R * C is always odd, so the median is a single elementThe intended solution is better than flattening and sortingInput: {"R":3,"C":3,"matrix":[[1,3,5],[2,6,9],[3,6,9]]}
Output: 5
Sorting the nine readings gives 1,2,3,3,5,6,6,9,9 and the middle one is 5.
Input: {"R":1,"C":3,"matrix":[[1,2,3]]}
Output: 2
A single bank of three readings is already sorted, so the median is its middle entry.