Search in a sorted 2D matrix ( Stored in row major order ) | Python 3 program to find whether a given element is present in the given 2 - D matrix ; Basic binary search to find an element in a 1 - D array ; if element found return true ; if middle less than K then skip the left part of the array else skip the right part ; if not found return false ; Function to search an element in a matrix based on Divide and conquer approach ; if the element lies in the range of this row then call 1 - D binary search on this row ; if the element is less then the starting element of that row then search in upper rows else search in the lower rows ; if not found ; Driver code
M = 3 NEW_LINE N = 4 NEW_LINE def binarySearch1D ( arr , K ) : NEW_LINE INDENT low = 0 NEW_LINE high = N - 1 NEW_LINE while ( low <= high ) : NEW_LINE INDENT mid = low + int ( ( high - low ) / 2 ) NEW_LINE if ( arr [ mid ] == K ) : NEW_LINE INDENT return True NEW_LINE DEDENT if ( arr [ mid ] < K ) : NEW_LINE INDENT low = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT high = mid - 1 NEW_LINE DEDENT DEDENT return False NEW_LINE DEDENT def searchMatrix ( matrix , K ) : NEW_LINE INDENT low = 0 NEW_LINE high = M - 1 NEW_LINE while ( low <= high ) : NEW_LINE INDENT mid = low + int ( ( high - low ) / 2 ) NEW_LINE if ( K >= matrix [ mid ] [ 0 ] and K <= matrix [ mid ] [ N - 1 ] ) : NEW_LINE INDENT return binarySearch1D ( matrix [ mid ] , K ) NEW_LINE DEDENT if ( K < matrix [ mid ] [ 0 ] ) : NEW_LINE INDENT high = mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT low = mid + 1 NEW_LINE DEDENT DEDENT return False NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT matrix = [ [ 1 , 3 , 5 , 7 ] , [ 10 , 11 , 16 , 20 ] , [ 23 , 30 , 34 , 50 ] ] NEW_LINE K = 3 NEW_LINE if ( searchMatrix ( matrix , K ) ) : NEW_LINE INDENT print ( " Found " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Not ▁ found " ) NEW_LINE DEDENT DEDENT