74. Search a 2D Matrix

一次二分法
class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        m,n=len(matrix),len(matrix[0])
        left,right=0,m*n-1
        while left<=right:
            mid=left+(right-left)/2
            if matrix[mid/n][mid%n]>target:
                right=mid-1
            elif matrix[mid/n][mid%n]==target:return True
            else: left=mid+1
           
        
        return False
            

两次二分法
class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        left,right=0,len(matrix)-1
        while left<=right:
            mid=left+(right-left)/2
            if matrix[mid][0]>target:
                right=mid-1
            elif matrix[mid][0]==target:return True
            else:
                left=mid+1
        #left is the first row that's larger than target 
        row=left-1
        print left-1
        left,right=0,len(matrix[0])-1
        while left<=right:
            mid=left+(right-left)/2
            if matrix[row][mid]>target:
                right=mid-1
            elif matrix[row][mid]==target:return True
            else:
                left=mid+1
        return False