Question

PYTHON

Search for an element in a 2D sorted matrix using the binary search technique. Your code should run in O(m + n) where m is the number of rows and n is the number of columns
The python file should have a function named binarysearch

The function should take two arguments. The first argument of the function will be the element to search for. Second argument of the function will be the matrix as a List[List].
The function should return the row and column of the matrix if the element is found. Use a tuple to return the row and column. Return "Not Found" if the element is not found.

Sample values for input and output :

Sample Input:
Case 1: binarysearch(4, [[1, 2, 3],[4, 5, 6],[7, 8, 9]] )
Case 2: binarysearch(10,[[2, 3, 4],[5, 7, 9],[11, 12, 13],[20, 22, 24]]

Sample Output :
Case 1: (1 , 0)
Case 2: Not Found

Answer 1

# in row-wise and column-wise sorted matrix
# Searches the element x in mat[][]. If the
# element is found, then return its position
# otherwise returns "not found"
def binarysearch(x,mat):
    i=0
    m=len(mat)

    j=len(mat[0])-1
    l=[]
    t=()
  
    while( i<m and j>=0):
        if(mat[i][j]==x):
            l.append(i)
            l.append(j)
            t=tuple(l)
            return t
      
        if ( mat[i][j] > x):
            j-=1
          
        if mat[i][j] < x:
            i+=1
    return "Not Found"  

# Driver Code
print("1st test case result:")
p=binarysearch(4, [[1, 2, 3],[4, 5, 6],[7, 8, 9]] )
print(p)
print("2nd test case result:")
p=binarysearch(10,[[2, 3, 4],[5, 7, 9],[11, 12, 13],[20, 22, 24]])
print(p)

OUTPUT:-

1st test case result:
(1, 0)
2nd test case result:
Not Found

The above approach complexity is O(m + n).