class Solution:

    def searchMatrix(self, matrix, target):

        if not matrix :

            return False

        row = len(matrix)

        col = len(matrix[0])

        i = 0

        j = col-1

        while i<row and j>=0:

            if matrix[i][j] == target:

                return True

            elif matrix[i][j] > target:

                j -= 1

            else:

                i += 1

        return False

class Solution:

    def searchMatrix(self, matrix, target):

        # an empty matrix obviously does not contain `target`

        if not matrix:

            return False

        def search_rec(left, up, right, down):

            # this submatrix has no height or no width.

            if left > right or up > down:

                return False

            # `target` is already larger than the largest element or smaller

            # than the smallest element in this submatrix.

            elif target < matrix[up][left] or target > matrix[down][right]:

                return False

            mid = left + (right-left)//2

            # Locate `row` such that matrix[row-1][mid] < target < matrix[row][mid]

            row = up

            while row <= down and matrix[row][mid] <= target:

                if matrix[row][mid] == target:

                    return True

                row += 1

            return search_rec(left, row, mid-1, down) or search_rec(mid+1, up, right, row-1)

        return search_rec(0, 0, len(matrix[0])-1, len(matrix)-1)