= Solution
Maintain a remaining rectangle with its top-right corner at `(i,j)`:
``
def searchMonotone(f: Array[Array[Int]], x: Int): Option[(Int, Int)] = {
val n = f.length
val m = if (n == 0) 0 else f(0).length
var i = 0
var j = m - 1
while (i < n && j >= 0) {
val v = f(i)(j)
if (v == x) return Some((i, j))
else if (v < x) i += 1
else j -= 1
}
None
}
``
The <loop invariant> is that any match must lie in rows $i,\ldots,n-1$ and columns $0,\ldots,j$. Smaller corner values exclude the current row, larger ones exclude the current column, as shown in part (d). The <loop variant> $(n-i)+(j+1)$ is nonnegative while the rectangle is nonempty and decreases by one on every unsuccessful inspection. When the loop exits, the rectangle is empty, so absence is established.
\b[At most $n+m-1$ entries are inspected when both dimensions are positive], giving $O(n+m)$ <running time> and $O(1)$ <auxiliary space>. An empty dimension causes no entry access. Duplicates do not affect the argument, since every exclusion uses a <strict inequality> relative to the target.
Back to article page
