class Solution(object):

def searchMatrix(self, matrix, target):

"""

:type matrix: List[List[int]]

:type target: int

:rtype: bool

"""

if not matrix or not matrix[0]:

return False

m=len(matrix)

n=len(matrix[0])

i=bisect.bisect_left(zip(*matrix)[-1],target)

if i<m:

j=bisect.bisect_left(matrix[i],target)

return matrix[i][j]==target

else:

return False