Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Imperative programming (resit) / 2 / d

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.