Search 2D matrix

这个题已经被反复讲过了，最好的办法就是从右上角开始，因为行列的有序性，当当前值小于target我们往下移动，大于则往左移动，如此就可以搜索整个矩阵，时间复杂度是O(lgmn)，此外如果用这种解法，search 2D matrix II就跟这道题没有区别了，下面是代码

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        n = len(matrix)
        if not n:
            return False

        m = len(matrix[0])
        if not m:
            return False

        row, col = 0, m - 1
        while row < n and col >= 0:
            cur = matrix[row][col]
            if cur < target:
                row += 1
            elif cur > target:
                col -= 1
            else:
                return True
        return False

Search 2D matrix II

跟上面那个一样，右上角开始二分搜索即可

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        n = len(matrix)
        if not n:
            return False

        m = len(matrix[0])
        if not m:
            return False

        row, col = 0, m - 1
        while row < n and col >= 0:
            if matrix[row][col] < target:
                row += 1
            elif matrix[row][col] > target:
                col -= 1
            else:
                return True
        return False