class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        m=len(matrix)
        if m==0:
            return False
        n=len(matrix[0])
        if n==0:
            return False
        i,j=m-1,0
        while i>=0 and j<n:
            if matrix[i][j]<target:
                j+=1
            elif matrix[i][j]>target:
                i-=1
            else:return True
        return False