= Solution
Without order information, inspect entries one row at a time:
``
def searchUnordered(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
while (i < n) {
var j = 0
while (j < m) {
if (f(i)(j) == x) return Some((i, j))
j += 1
}
i += 1
}
None
}
``
The outer <loop invariant> excludes every entry in earlier rows; the inner one also excludes columns before `j` in the current row. Failed <equality tests> preserve these exclusions. The inner and outer <loop variants> are $m-j$ and $n-i$, respectively. A successful return identifies an actual match, while exhaustion excludes the entire <array>. At most $nm$ entries are inspected.
The source's “at least $O(nm)$” should be read as a worst-case \b[$\Omega(nm)$ lower bound], using the correct asymptotic direction. If any entry were left unread on an all-nonmatching input, changing only that entry to $x$ would leave the observations identical while changing the answer. Thus every always-correct procedure needs $nm$ inspections in the worst case, and this algorithm achieves $\Theta(nm)$ entry inspections. Empty dimensions return absence; the asymptotic claim concerns nonempty arrays.
Back to article page
