74. 搜索二维矩阵

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

方法二

利用矩阵的递增性质

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if len(matrix) == 0:
            return False
        m = len(matrix)
        n = len(matrix[0])
        
        low = 0
        high = m*n-1
        
        while low<=high:
            mid = low + (high-low)/2
            row = mid/n
            col = mid%n
            if(matrix[row][col]> target):
                high = mid -1
            elif(matrix[row][col]<target):
                low = mid+1
            else:
                return True
        return False