781. The Middle Value of a Row-Sorted Grid

An R by C grid is given whose ROWS are each non-decreasing. Imagine all R * C values written out in sorted order, duplicates included. Print the value standing at position (R * C + 1) / 2, using integer division and counting positions from 1.

When R * C is odd that is the median. When it is even it is the lower of the two middle values.

``` grid 1 3 5 2 6 9 3 6 9 9 values, position 5 -> 5

grid 1 2 3 4 4 values, position 2 -> 2

grid 1 1 9 1 1 9 1 1 9 1 1 9 12 values, position 6 -> 1

grid -5 -5 -5 -1 -1 7 6 values, position 3 -> -5 ```

## Why "half of them are below it" is the wrong predicate

The tempting definition of a median is "the value with half the data below it". Written as a predicate that is countLess(x) == half, and on duplicate-heavy input it has NO solution.

Take 1 1 9 / 1 1 9 / 1 1 9 / 1 1 9. Eight ones, four nines, twelve values, wanted position 6. The number of values strictly below 1 is 0 and strictly below 9 is 8. Nothing has 5 below it, so a search for an exact split runs to the end of its range and returns whatever bound it happens to be holding.

The fix is to stop describing the answer and start counting: the answer is the smallest x with count(x) >= (R * C + 1) / 2, where count is "at most x", not "strictly below x". That definition has a solution on every input, and it is the same definition #779 uses for a general k. This problem is that one with k fixed at the middle, kept separate because the median is where the exact-split mistake actually gets made.

## The counter

Each row is sorted, so the number of entries at most x in a row is one binary search. Summed over rows that is O(R log C) per guess, and it is non-decreasing in x because raising the threshold can only admit more entries.

## Why the answer occurs in the grid

At the stopping point count(x) >= need and count(x - 1) < need, so some entry lies in (x - 1, x]. Entries are integers, so an entry equals x. The grid 2 2 2 / 2 2 2 / 2 2 2 and the grid of ones and nines above are both in the tests for exactly this reason.

## The bounds

lo is the smallest first-column entry and hi the largest last-column entry.

## The boundary that breaks a careless implementation

(R * C + 1) / 2 must be integer division and it must be + 1 before the divide. Using R * C / 2 gives 4 rather than 5 on a 9-cell grid and returns the value one place too early; the mistake is invisible on every even-sized grid, so it survives casual testing.

## Relationship with problem 870

870 wants a median too, and gets it from two heaps that hold the smaller half and the larger half apart from each other. That shape is forced by its input: values ARRIVE one at a time and a median is wanted after each one, so the structure has to be maintained rather than computed.

This problem has every value in front of it from the start and still refuses to put them in order, because R * C reaches 10^6 and exactly one rank is wanted. The definitions differ at the even case as well: 870 averages the two middle values and prints a decimal, while this takes the LOWER of the two and prints an integer, which is what allows the whole thing to be a lower-bound search over values.

## Where the 32-bit ceiling actually is

Values span -10^9 to 10^9, so hi - lo reaches 2000000000 and lo + hi reaches the same magnitude, both inside the 2147483647 a signed integer held in 32 bits reaches. R * C caps the count at 10^6. No part of this problem needs a wider type.

The bounds still have to be handled with care, for a reason that has nothing to do with width. Values may be negative and integer division in C, C++ and Java truncates TOWARDS ZERO, so mid = (lo + hi) / 2 rounds the wrong way once the range is entirely negative. On -5 -5 -5 / -1 -1 7 it settles at lo = -5, hi = -4, where -9 / 2 truncates to -4, hi is set to the value it already held, and the loop never terminates. Write mid = lo + (hi - lo) / 2, where hi - lo is positive for as long as the loop runs.

## Cost

Time O(R log C log(range)). Space O(1) beyond the grid.

Constraints - `1 ≤ R, C ≤ 1000` - `-10^9 ≤ each value ≤ 10^9` - every row is non-decreasing