When does binary searching every row of a row- and column-sorted grid beat the O(m+n) walk?

## Two costs, written out For an m x n grid sorted along every row and every column, three methods are on the table: | Method | Probes | Uses column ordering? | Extra space | |---|---|---|---| | Scan every cell | m·n | no | O(1) | | Corner elimination from the top-right | m + n | yes | O(1) | | Binary search each row | m·log n | no | O(1) | The interview question is almost never "which is fastest" in the abstract; it is "under which shapes does each one win", because that is where a candidate reveals whether they read asymptotics as slogans or as arithmetic. ## Solving the comparison Per-row binary search beats the corner walk exactly when ``` m * log n < m + n ``` which rearranges to `m * (log n - 1) < n`. Read it directly: the row count sits **outside** the logarithm and multiplies it, so it is the row count that decides. The method wins when m is small relative to n / log n — a short, wide grid. Concrete shapes, using base-2 logarithms: | Shape | Corner walk (m+n) | Per-row search (m·log n) | Winner | |---|---|---|---| | 4 x 1,000,000 | ~1,000,004 | ~80 | per-row, by four orders of magnitude | | 1,000 x 1,000 | ~2,000 | ~10,000 | corner walk | | 1,000,000 x 8 | ~1,000,008 | ~3,000,000 | corner walk | The middle row is the one that matters most in practice: on a square grid — the default mental image — the corner walk wins, which is why it is taught as the answer. But the answer is conditional, and a senior candidate says so. ## The misconception being tested The reflex is "logarithmic beats linear, so binary search wins". Two things are wrong with it. First, `m·log n` is not logarithmic in the input size at all; it is *linear in the row count*, with a logarithmic factor attached. Second, `m + n` is not linear in the cell count either — it is linear in the grid's **perimeter**, which is already an enormous saving against m·n. Comparing an O(m log n) label to an O(m+n) label without substituting the actual dimensions is exactly the failure mode. Asymptotic notation compares growth in *one* parameter; with two parameters you must decide how they relate before any comparison is meaningful. ## What per-row search quietly gives up, and gains It never consults the column ordering. That is a loss — it throws away half the guarantee — but it is also a gain in applicability: the method remains correct on a grid where only the rows are sorted and columns are arbitrary, which the corner walk cannot handle at all. If a data contract promises only per-row ordering, per-row binary search is not a fallback, it is the method. When the column ordering *does* hold, you can prune before searching. The first entries of the rows are non-decreasing top to bottom, and so are the last entries; therefore the rows that could possibly contain the target — those whose first entry does not exceed it and whose last entry is not below it — form a **contiguous band**. Two binary searches over the row boundaries, O(log m) each, locate that band. In practice this often shrinks the work enormously. It does not improve the worst case: an adversarial grid can put every row in the band, leaving m·log n again. ## Choosing under a real constraint When a probe is cheap — the grid is a small in-memory block — probe counts barely matter and either method is fine; pick the one you can explain and test. When each probe is expensive, because a cell fetch crosses a network or a storage boundary, the probe count *is* the latency budget and the shape analysis above becomes the deciding argument. State which regime you are in before you pick, and say what would change your mind: for a grid whose aspect ratio varies at run time, the honest answer is to branch on the measured dimensions rather than hard-code one method. Neither simple method is optimal for every aspect ratio. More elaborate divide-and-conquer strategies do better than both on strongly skewed shapes; they are rarely worth the implementation and testing cost unless the search is genuinely hot, and knowing where that line sits is the judgment being examined. ## What a strong answer sounds like "The corner walk is m + n and per-row binary search is m·log n, so the question is the aspect ratio. For anything near-square or taller than wide, the walk wins and I would default to it. For a short, wide grid — a handful of rows across a very long span — per-row search wins by orders of magnitude, and I would also reach for it if the contract only promises row ordering. If the column ordering holds I would first narrow to the contiguous band of candidate rows in logarithmic time, which usually collapses the constant even though it does not change the worst case."