Question

In this program, use binary search to search for an element in 2D sorted matrix, the program should include binary search which has two arguments(element to search, and matrix as a List [List])

The Binary search 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 exist

Please comment the code

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

Python Program:

def binarySearchRecursive(mat, i, jLow, jHigh, ele):
   # Iterating over part of list
   while (jLow <= jHigh):
       # Calculating middle element
       jMid = int((jLow + jHigh) / 2)
       # Element found
       if (mat[i][jMid] == ele):
           return (i, jMid)
       # Left Sub List
       elif (mat[i][jMid] > ele):
           jHigh = jMid - 1
       # Right Sub List
       else:
           jLow = jMid + 1
      
   # If element is not found
   return "Element not found"
      

def binarysearch(ele, mat):
   # Finding number of rows and columns
   rows = len(mat)
   cols = len(mat[0])
   # Checking number of rows
   if (rows == 1):
       return binarySearchRecursive(mat, 0, 0, cols-1, ele)
  
   # Initializing values
   iLow = 0
   iHigh = rows - 1
   # Calculating middle position
   jMid = int(cols / 2)
   # Iterating over array
   while ((iLow + 1) < iHigh):
       # Middle index
       iMid = int((iLow + iHigh) / 2)
       # Comparing values
       if (mat[iMid][jMid] == ele):
           return (iMid, jMid)
       elif (mat[iMid][jMid] > ele):
           iHigh = iMid
       else:
           iLow = iMid
  
   # If element is found
   if (mat[iLow][jMid] == ele):
       return (iLow, jMid)
   elif (mat[iLow + 1][jMid] == ele):
       return (iLow+1, jMid)
   # Searching for element on 1st half of 1st row
   elif (ele <= mat[iLow][jMid - 1]):
       return binarySearchRecursive(mat, iLow, 0, jMid - 1, ele)
   # Searching for element on 2nd half of 1st row
   elif (ele >= mat[iLow][jMid + 1] and ele <= mat[iLow][cols - 1]):
       return binarySearchRecursive(mat, iLow, jMid + 1, cols - 1, ele)
   # Searching for element on 1st half of 2nd row
   elif (ele <= mat[iLow + 1][jMid - 1]):
       return binarySearchRecursive(mat, iLow + 1, 0, jMid - 1, ele)
   # Searching for element on 2nd half of 2nd row
   else:
       return binarySearchRecursive(mat, iLow + 1, jMid + 1, cols - 1, ele)

      
# Testing functions
print(binarysearch(4, [[1, 2, 3],[4, 5, 6],[7, 8, 9]]))
print(binarysearch(10,[[2, 3, 4],[5, 7, 9],[11, 12, 13],[20, 22, 24]]))

____________________________________________________________________________________________

Code Screenshot:

____________________________________________________________________________________________

Sample Run: