<s> """<STR_LIT>""" <EOL> __author__ = '<STR_LIT>' <EOL> class Solution ( object ) : <EOL> def searchMatrix ( self , mat , target ) : <EOL> """<STR_LIT>""" <EOL> m = len ( mat ) <EOL> n = len ( mat [ <NUM_LIT:0> ] ) <EOL> i = <NUM_LIT:0> <EOL> j = n - <NUM_LIT:1> <EOL> while i < m and <NUM_LIT:0> <= j : <EOL> if mat [ i ] [ j ] == target : <EOL> return True <EOL> elif mat [ i ] [ j ] > target : <EOL> j -= <NUM_LIT:1> <EOL> else : <EOL> i += <NUM_LIT:1> <EOL> return False <EOL> class SolutionBinSearch ( object ) : <EOL> def searchMatrix ( self , mat , target ) : <EOL> """<STR_LIT>""" <EOL> m = len ( mat ) <EOL> n = len ( mat [ <NUM_LIT:0> ] ) <EOL> col = [ mat [ i ] [ <NUM_LIT:0> ] for i in xrange ( m ) ] <EOL> row_by_first = self . bin_search ( col , target ) <EOL> col = [ mat [ i ] [ - <NUM_LIT:1> ] for i in xrange ( m ) ] <EOL> row_by_last = self . bin_search ( col , target , False ) <EOL> for i in range ( row_by_first , row_by_last - <NUM_LIT:1> , - <NUM_LIT:1> ) : <EOL> col = self . bin_search ( mat [ i ] , target ) <EOL> if mat [ i ] [ col ] == target : <EOL> return True <EOL> return False <EOL> def bin_search ( self , A , t , lower = True ) : <EOL> lo = <NUM_LIT:0> <EOL> hi = len ( A ) <EOL> while lo < hi : <EOL> mid = ( lo + hi ) / <NUM_LIT:2> <EOL> if A [ mid ] == t : <EOL> return mid <EOL> elif A [ mid ] < t : <EOL> lo = mid + <NUM_LIT:1> <EOL> else : <EOL> hi = mid <EOL> if lower : <EOL> return lo - <NUM_LIT:1> <EOL> else : <EOL> return lo <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> assert Solution ( ) . searchMatrix ( [ [ <NUM_LIT:1> , <NUM_LIT:4> ] , [ <NUM_LIT:2> , <NUM_LIT:5> ] ] , <NUM_LIT:4> ) == True <EOL> assert SolutionBinSearch ( ) . searchMatrix ( [ [ <NUM_LIT:1> , <NUM_LIT:4> ] , [ <NUM_LIT:2> , <NUM_LIT:5> ] ] , <NUM_LIT:4> ) == True </s>
