 Staircase matrix search

Search a matrix whose rows and columns are both nondecreasing by inspecting the top-right corner of the remaining rectangle. If that value is below the target, discard its row; if above, discard its column; if equal, return its coordinates. The loop invariant retains every possible match inside the rectangle. Each failure decreases its remaining height plus width by one, proving at most $n+m-1$ inspections for positive dimensions and constant auxiliary space. Row monotonicity alone is insufficient for the column exclusion.