Python Solution(beat over 99.34%) Binary Search


  • 0
    J
    def searchMatrix(self, matrix, target):
            """
            :type matrix: List[List[int]]
            :type target: int
            :rtype: bool
            """
            try:
                N, M = len(matrix), len(matrix[0])
                if(N == 1 and M == 1):
                    return True if matrix[0][0] == target else False
                l, r = 0, N * M
                while(l < r):
                    mid = (l + r) >> 1
                    row, col = divmod(mid, M)
                    middle = matrix[row][col]
                    if(middle == target):
                        return True
                    elif(middle > target):
                        r = mid
                    else:
                        l = mid + 1
                return False
            except:
                return False
    

    (1)use "try except" to handle special cases.
    (2)use "divmod" to reduce the division operation to only once instead of using / and %


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.