817. One Search Over the Whole Grid
A grid has m rows and n columns. Reading it row by row, left to right, top to bottom,
produces a strictly increasing sequence. So each row is increasing, and the last entry of every
row is smaller than the first entry of the row below it.
Given x, print the row and column where it sits, 0-based, or -1 -1 if it is absent.
1 3 5 7
10 11 16 20 x = 3 -> 0 1
23 30 34 60 x = 13 -> -1 -1
## Do not search the rows and then the row
The tempting plan is: binary search the first column to pick a row, then binary search inside
that row. It works, it costs O(log m + log n), and it needs two loops with two different
boundary conventions, which is two chances to get the off-by-one wrong.
The whole grid is ALREADY one sorted sequence. Search it as one.
## The index mapping
Treat the grid as a virtual list of m * n entries. Virtual index i holds
row = i / n (integer division)
column = i % n
Note both use n, the number of COLUMNS, and neither uses m. Dividing by m is the single
most common mistake here, and it is invisible on a square grid, which is why the tests include
a one-row grid and a one-column grid.
## The invariant the loop maintains
Run the lower bound from problem 241 over the virtual indices, with lo = 0 and hi = m * n,
keeping:
> the first virtual index whose value is at least x lies in [lo, hi].
hi starts at m * n and not m * n - 1, because the answer to "where would x go?" can
legitimately be one past the end, and a hi of m * n - 1 can never return it.
## Why the loop terminates
mid = lo + (hi - lo) / 2 satisfies lo <= mid < hi while lo < hi. The branch
value < x sets lo = mid + 1, strictly above the old lo; the other sets hi = mid,
strictly below the old hi. So the gap closes and the loop ends with lo == hi.
## What is printed when nothing qualifies
The lower bound returns a POSITION, never a verdict. Two things can go wrong with it and both must be checked, in this order:
lo == m * n every entry is smaller than x
a[lo] != x x would go here, but it is not here
Checking a[lo] != x first reads past the end of the grid when lo == m * n. In C that is
undefined behaviour and in Java it throws. Either way, both cases print -1 -1.
## Overflow
m * n reaches 10^6, which is comfortable in 32 bits, but lo + hi reaches 2 * 10^6,
so the habit of writing lo + (hi - lo) / 2 costs nothing and keeps working when the grid
grows.
## Related problems
Problem 241 is this lower bound on a plain list, and problem 261 is the same loop read as an insertion point. The only new idea here is the index mapping. Problem 818 drops the promise that one row ends below the next begins, and the single-search trick collapses entirely.
## Cost
Time O(log(m * n)). Space O(m * n) for the grid.
Constraints - `1 ≤ m ≤ 1000` - `1 ≤ n ≤ 1000` - `m * n ≤ 1000000` - `-1000000000 ≤ a[i][j] ≤ 1000000000` - Read row by row, the grid is strictly increasing.
Input
The first line contains three integers m, n and x, the number of rows, the number of columns, and the value to find.
The next m lines each contain n integers, one row of the grid.
Output
Print two integers separated by one space: the 0-based row and the 0-based column holding x. If x is absent, print -1 -1 instead. One line either way.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.