def search(f: Array[Array[Int]], x: Int): Option[(Int, Int)]Some((i,j)) denotes a match; None denotes absence. The extra array argument makes the dependence on the searched data explicit; if f is already enclosed in the surrounding scope, it can instead be omitted. For all implementations below, assume f is non-null, its rows are non-null and rectangular, and it remains unchanged during the search. Empty dimensions are permitted.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 and , respectively. A successful return identifies an actual match, while exhaustion excludes the entire array. At most entries are inspected.The source's “at least ” should be read as a worst-case lower bound, using the correct asymptotic direction. If any entry were left unread on an all-nonmatching input, changing only that entry to would leave the observations identical while changing the answer. Thus every always-correct procedure needs inspections in the worst case, and this algorithm achieves entry inspections. Empty dimensions return absence; the asymptotic claim concerns nonempty arrays.
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 , with every value before
lo smaller than and every value from hi onward at least . 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 . Failure extends the outer exclusion.The cost is , conventionally written for ; the extra one matters when a row has a single entry. Storage is constant. The source's column ranges must use indices strictly below , since
f(i)(m) is outside the array.Assume both dimensions are positive so the top-right entry exists. If
f(0)(m-1) == x, it is already a match. If it is smaller than , the entire first row is smaller, since it is that row's maximum; discard the first row. If it is larger than , the entire last column is larger, since it is that column's minimum; discard the last column. This is the staircase matrix search elimination step. Row and column monotonicity are both needed for the respective conclusions.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 and columns . Smaller corner values exclude the current row, larger ones exclude the current column, as shown in part (d). The loop variant 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 entries are inspected when both dimensions are positive, giving running time and 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.
Articles by others on the same topic
There are currently no matching articles.