Solution

Use a lower-bound search separately in each nondecreasing row:

def searchRows(f: Array[Array[Int]], x: Int): Option[(Int, Int)] = {
  val n = f.length
  val m = if (n == 0) 0 else f(0).length
  if (m == 0) return None
  var i = 0
  while (i < n) {
    var lo = 0
    var hi = m
    while (lo < hi) {
      val mid = lo + (hi - lo) / 2
      if (f(i)(mid) < x) lo = mid + 1
      else hi = mid
    }
    if (lo < m && f(i)(lo) == x) return Some((i, lo))
    i += 1
  }
  None
}

The outer loop invariant says there is no match in earlier rows. The inner invariant is

0 \leq l o \leq hi \leq m

, with every value before lo smaller than

x

and every value from hi onward at least

x

. Sortedness justifies each exclusion, and hi - lo strictly decreases. At exit, a match in this row exists exactly when the lower-bound index is inside the row and holds