In a virtual-1D binary search over a fully sorted grid, why does mid map through the column count?

## The virtual coordinate system When a grid is fully sorted — each row non-decreasing, and every row starting at or above where the previous row ended — the reading-order sequence of its cells is one sorted sequence. Binary search only needs three things: a total order, random access by position, and a way to compare a probed position to the target. The grid already gives all three; the only missing piece is a translation between a *flat position* and a *cell*. Number the cells in reading order: cell (0,0) is flat position 0, (0,1) is 1, ..., (0, cols−1) is cols−1, and (1,0) is cols. The pattern is immediate — each new row begins exactly `cols` positions after the previous row began. So the number of complete rows before flat position `i` is `i / cols` under integer division, and what remains, `i % cols`, is the offset within that row. ``` row = mid / cols column = mid % cols ``` ## Why `rows` is the tempting wrong divisor The two dimension counts sit next to each other in the signature and both feel like "the size of the thing", so `mid / rows` gets written constantly. It is wrong for a reason worth stating precisely: the divisor must be the **stride**, the distance in flat positions between the start of consecutive rows, and that distance is the row's length — the column count. The bug is unusually durable because on a **square** grid `rows == cols`, so every probe is right and every test is green. It surfaces the first time someone searches a wide grid (say 3 rows by 40 columns, where `mid / rows` overshoots the row index by more than ten times and the column offset wraps nonsensically) or a tall one (where the computed row index stays far too small and the search converges on the wrong cell, returning a wrong "not found" or, worse, a wrong hit). Make your fixtures non-square on purpose; a 1×n and an m×1 grid are the two cheapest tests that catch it. ## The window boundaries There are `rows*cols` cells, so valid flat positions run `0` through `rows*cols − 1`. With the inclusive form of the loop (`while lo <= hi`), `hi` starts at `rows*cols − 1`. Initialising `hi = rows*cols` makes the first midpoint reachable one past the last cell on some inputs and turns a clean search into an out-of-range probe. The half-open variant (`lo < hi` with `hi = rows*cols`) is equally valid, but then the loop exits with a *candidate* rather than a verdict and you must compare the surviving position to the target once at the end. Pick one form and keep its invariant straight rather than mixing them. Use `mid = lo + (hi - lo) / 2` rather than `(lo + hi) / 2`. On a grid with a billion cells the sum can exceed the range of a fixed-width index type; the subtractive form never exceeds `hi`. ## Guard the degenerate shapes first If `rows == 0`, or if the grid has rows but `cols == 0`, then `rows*cols == 0` and `hi` becomes −1; with the inclusive loop that is harmless (the loop body never runs) but any code that probes before checking will divide by zero or index nothing. Handle the empty grid explicitly. The mapping also assumes every row has the same length. On a **jagged** grid — rows of differing lengths — there is no single stride, so flat position `i` cannot be decomposed by one division at all. The whole virtual-array technique requires a rectangular grid; if the input is jagged, you either normalise it or fall back to a different method, and saying so unprompted is a good signal. ## Never materialise the flattening A frequent misstep is to copy the grid into a real one-dimensional sequence and binary search that. It is correct, but it costs O(mn) time and O(mn) extra space to set up a search that was going to cost O(log mn) — you have paid a linear price to avoid two arithmetic operations. The virtual mapping exists precisely so that no copy happens; the flat sequence is a coordinate system, not a data structure. ## The two-stage alternative If the modular arithmetic feels error-prone, the same O(log mn) is reachable in two stages without it: binary search the **first column** for the last row whose first entry is at most the target, then binary search inside that single row. That is O(log m) + O(log n), the same total, and each stage is an ordinary binary search over an ordinary sequence. It is a perfectly good answer, and offering both shows you understand that O(log mn) and O(log m + log n) are the same bound written differently.