 Solution

Assume both dimensions are positive so the top-right entry exists. If 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.