Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Imperative programming (resit) / 2 / e / 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,\dots ,n-1$ and columns $0,\dots ,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.

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.