Find Median in Row-wise Sorted Matrix
Using Binary Search

Matrix	Rows × Cols	Median	Description
[[1, 3, 5], [2, 6, 9], [3, 6, 9]]	3 × 3	5	Sorted order: [1, 2, 3, 3, 5, 6, 6, 9, 9], middle element is 5
[[1, 3], [2, 4]]	2 × 2	2	Sorted: [1, 2, 3, 4], lower middle is 2
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]	3 × 3	5	Already fully sorted matrix, 5 is the center
[[10, 20, 30], [5, 15, 25], [1, 2, 3]]	3 × 3	10	Unordered globally, but each row is sorted. Full order: [1, 2, 3, 5, 10, 15, 20, 25, 30]
[[1]]	1 × 1	1	Only one element
[[1, 2, 3]]	1 × 3	2	Single row
[[1],[2],[3]]	3 × 1	2	Single column
[]	0 × 0	null	Empty matrix, no elements
[[]]	1 × 0	null	One row but zero columns

To find the median in a row-wise sorted matrix, we need to look at the overall distribution of values across the entire matrix—not just within rows. A naive way would be to flatten all elements, sort them, and pick the middle one. But this approach is inefficient for large matrices.

Understanding the Median

The median is the element that would appear in the middle if all elements were lined up in a single sorted list. For example, in a 3×3 matrix, the 5th smallest element is the median. In a 4×4 matrix, it's the 8th smallest element (as we take the lower middle).

Why Binary Search Works

Instead of sorting all values, we can use binary search on the value range itself—between the smallest and largest elements of the matrix. This range is not about indices but about actual values.

At every step, we guess a potential median (say mid) and count how many elements in the matrix are ≤ mid. Since rows are sorted, we can do this efficiently row by row using techniques like upper_bound.

If the count is less than or equal to half of the total number of elements, it means the actual median must be higher—so we move the search window to the right. If the count is greater, the median must be smaller or equal—so we move left.

Different Cases to Consider

• Normal matrix: Works perfectly because all rows are sorted.
• Single row or single column: Still valid, as binary search does not depend on 2D ordering but on total count.
• Even number of total elements: We return the lower middle element (e.g., 2nd of 4).
• Matrix with one element: That element is the median.
• Empty matrix: There's no valid median, so we return null.

Efficiency

This approach avoids flattening and sorting the entire matrix, which could take O(N log N) time. Instead, it uses binary search over value range, and counts efficiently row-by-row, giving a much better time complexity of O(32 × R × log C), where 32 is the number of bits (since we search over integers).