= Solution
Assume both dimensions are positive so the top-right entry exists. If \b[`f(0)(m-1) == x`], it is already a match. If it is smaller than $x$, the entire first row is smaller, since it is that row's maximum; discard the first row. If it is larger than $x$, the entire last column is larger, since it is that column's minimum; discard the last column. This is the <staircase matrix search> elimination step. Row and column monotonicity are both needed for the respective conclusions.
Back to article page
