3. Let M be an n x n matrix containing the numbers 1,2,... , n2. The n integers of each row of M are sorted in an increasing order (from left to right) and the n integers of each column of M are sorted in an increasing order (from top to bottom) Lot l #5T12 be an unknown numbers. The goal is to find the position M[i,j] of z in M (z is in row i and column j) using only comparisons between r and integers in the matrix. (a) Describe an algorithm that always finds the position of r with O(n) comparisons. Explain why your algorithm is correct and justify why it is a inear time algorithm