In this problem we consider searching for some instance) of a number in a 2-dimensional array. The array is "semi-sorted in the following sense: the elements in each row appear in increasing order and the elements in each column appear in the decreasing order. For instance, the following array is a semi-sorted array.
10 14 15
7 8 10
2 4 9
1 5 5
(Here A[1,1]=10 and A[4,3)=5.) // Search for the number x in a semi-sorted 2D array A, // among Alij) in the range defined by asism and bss n. 2DSearch(A, x, a, b, m, n) {
if (a>m or b>n) // Empty range return "Not found"
y := A[a,b]
if x=y return (a,b) i
if x < y theb
return 2d search (A,xa+1b,m,n)
else
return 2d search (A,xa+1b,m,n)
}
Let T (m.n) be the wordh case time taken by 2D search on input (A,x,1,1,m,n) then T (m,n)
Select one
A. θ (m,n)
B. θ (m^2+n^2 )
C. θ 〖(log〗〖m+log〖n)〗 〗
D. θ(mn(log〖m+〖logn))〗 〗
E. θ(Mlog m+n log〖n))〗
F. θ (mn)
