CS计算机代考程序代写 186 (sorted two-dimensional search) Write a program to find a given item in a given 2- dimensional array in which each row is sorted and each column is sorted. The execution time must be linear in the sum of the dimensions.

186 (sorted two-dimensional search) Write a program to find a given item in a given 2- dimensional array in which each row is sorted and each column is sorted. The execution time must be linear in the sum of the dimensions.
§ Letthearraybe A,letitsdimensionsbe n by m,andlettheitemweseekbe x.The problem, except for time, is P , where
P = if x: A(0,..n)(0,..m) then x = Aiʹjʹ else iʹ=–1 ∨ jʹ=m fi
The idea is to start at the lower left corner of the array, and by comparing that item with x we can cross off an entire row or column, and then repeat. We’ll need integer variables i and j to keep track of the row and column. Define
Q = –1≤i x then i:= i–1. Q
else ifAij x ∧ (i:= i–1. Q) i⧧–1∧j⧧m∧Aij>x∧(i:=i–1. Q)∧–1≤ix∧(i:=i–1. Q)
if x: A(0,..i+1)(j,..m) then x = Aiʹjʹ else iʹ=–1 ∨ jʹ=m fi
expand first Q , portation simplify antecedent expand Q , substitution
Q
=⊤
0≤i x
∧ (–1≤i–1 x
∧ if x: A(0,..i)(j,..m) then x = Aiʹjʹ else iʹ=–1 ∨ jʹ=m fi
if x: A(0,..i+1)(j,..m) then x = Aiʹjʹ else iʹ=–1 ∨ jʹ=m fi If Aij > x and
row i is sorted, then ¬ x: Ai(j,..m) and so x: A(0,..i)(j,..m) = x: A(0,..i+1)(j,..m) =⊤
⇐ i⧧–1∧j⧧m∧Aij