= Solution
Implement <staircase matrix search> from the top-right corner. In the following <Oberon>-style code, `&` denotes short-circuit conjunction; all guarded accesses respect <array bounds>.
``
PROCEDURE Staircase(x: INTEGER; VAR i, j: INTEGER): BOOLEAN;
VAR r, c: INTEGER;
BEGIN
r := 0; c := N-1;
WHILE (r < M) & (c >= 0) DO
IF f[r,c] = x THEN i := r; j := c; RETURN TRUE
ELSIF f[r,c] < x THEN INC(r)
ELSE DEC(c)
END
END;
RETURN FALSE
END Staircase;
``
The <loop invariant> is that every occurrence not yet returned lies in
$$
[r,M)\times[0,c+1).
$$
Initially this is the whole <array>. If $f[r,c]<x$, every entry of row $r$ in the candidate rectangle is smaller than $x$, so increasing $r$ discards no possible answer. If $f[r,c]>x$, every entry of column $c$ in that rectangle is greater than $x$, so decreasing $c$ is safe. These conclusions follow from <monotonicity> even when repeated values occur.
The <loop variant> $(M-r)+(c+1)$ decreases on every unsuccessful iteration. If a dimension becomes empty, the <loop invariant> proves absence. For positive dimensions the path inspects at most $M+N-1$ entries; an initially empty dimension causes no inspection. Thus
$$
\boxed{\text{Time }O(M+N),\qquad\text{auxiliary space }O(1).}
$$
Back to article page
