Given an N x N matrix M with binary entries i.e every entry is either 1 or 0. You are told that every row and every column is sorted in increasing order. You are required to output a pair (i,j) with 1 <= i and j <= n corresponding to the entry of the matrix satisfying Mij = 1 and
Mrs = 0 for all 1 <= r <= i and 1 <= s <= j except for Mij
Informally this includes the entry of M = 1 and is closest to the top left corner.
for example:
M = [ 0 0 0 1
0 0 1 1
0 0 1 1
0 0 1 1]
output is (2,3) or (1,4)
M = [ 0 1 1
1 1 1
1 1 1]
output could be (1,2) or (2,1)
Design a divide and conquer algorithm, explain correctness and runtime of the algorithm.
