Search element in a sorted matrix | Python3 implementation to search an element in a sorted matrix ; This function does Binary search for x in i - th row . It does the search from mat [ i ] [ j_low ] to mat [ i ] [ j_high ] ; Element found ; Element not found ; Function to perform binary search on the mid values of row to get the desired pair of rows where the element can be found ; Single row matrix ; Do binary search in middle column . Condition to terminate the loop when the 2 desired rows are found ; element found ; If element is present on the mid of the two rows ; search element on 1 st half of 1 st row ; Search element on 2 nd half of 1 st row ; Search element on 1 st half of 2 nd row ; Search element on 2 nd half of 2 nd row ; Driver program to test above
MAX = 100 NEW_LINE def binarySearch ( mat , i , j_low , j_high , x ) : NEW_LINE INDENT while ( j_low <= j_high ) : NEW_LINE INDENT j_mid = ( j_low + j_high ) // 2 NEW_LINE if ( mat [ i ] [ j_mid ] == x ) : NEW_LINE INDENT print ( " Found ▁ at ▁ ( " , i , " , ▁ " , j_mid , " ) " ) NEW_LINE return NEW_LINE DEDENT elif ( mat [ i ] [ j_mid ] > x ) : NEW_LINE INDENT j_high = j_mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT j_low = j_mid + 1 NEW_LINE DEDENT DEDENT print ( " Element ▁ no ▁ found " ) NEW_LINE DEDENT def sortedMatrixSearch ( mat , n , m , x ) : NEW_LINE INDENT if ( n == 1 ) : NEW_LINE INDENT binarySearch ( mat , 0 , 0 , m - 1 , x ) NEW_LINE return NEW_LINE DEDENT i_low = 0 NEW_LINE i_high = n - 1 NEW_LINE j_mid = m // 2 NEW_LINE while ( ( i_low + 1 ) < i_high ) : NEW_LINE INDENT i_mid = ( i_low + i_high ) // 2 NEW_LINE if ( mat [ i_mid ] [ j_mid ] == x ) : NEW_LINE INDENT print ( " Found ▁ at ▁ ( " , i_mid , " , ▁ " , j_mid , " ) " ) NEW_LINE return NEW_LINE DEDENT elif ( mat [ i_mid ] [ j_mid ] > x ) : NEW_LINE INDENT i_high = i_mid NEW_LINE DEDENT else : NEW_LINE INDENT i_low = i_mid NEW_LINE DEDENT DEDENT if ( mat [ i_low ] [ j_mid ] == x ) : NEW_LINE INDENT print ( " Found ▁ at ▁ ( " , i_low , " , " , j_mid , " ) " ) NEW_LINE DEDENT elif ( mat [ i_low + 1 ] [ j_mid ] == x ) : NEW_LINE INDENT print ( " Found ▁ at ▁ ( " , ( i_low + 1 ) , " , ▁ " , j_mid , " ) " ) NEW_LINE DEDENT elif ( x <= mat [ i_low ] [ j_mid - 1 ] ) : NEW_LINE INDENT binarySearch ( mat , i_low , 0 , j_mid - 1 , x ) NEW_LINE DEDENT elif ( x >= mat [ i_low ] [ j_mid + 1 ] and x <= mat [ i_low ] [ m - 1 ] ) : NEW_LINE binarySearch ( mat , i_low , j_mid + 1 , m - 1 , x ) NEW_LINE elif ( x <= mat [ i_low + 1 ] [ j_mid - 1 ] ) : NEW_LINE INDENT binarySearch ( mat , i_low + 1 , 0 , j_mid - 1 , x ) NEW_LINE DEDENT else : NEW_LINE INDENT binarySearch ( mat , i_low + 1 , j_mid + 1 , m - 1 , x ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 4 NEW_LINE m = 5 NEW_LINE x = 8 NEW_LINE mat = [ [ 0 , 6 , 8 , 9 , 11 ] , [ 20 , 22 , 28 , 29 , 31 ] , [ 36 , 38 , 50 , 61 , 63 ] , [ 64 , 66 , 100 , 122 , 128 ] ] NEW_LINE sortedMatrixSearch ( mat , n , m , x ) NEW_LINE DEDENT