Python Binary Search Beats 100%, very simple explaination.


  • 0
    D

    All we're doing is binary search, but transforming our index we use in a 1D array into that of the indices of the 2D array.
    If we have a 3 by 4 2D array as such:
    (0,0) (0,1) (0,2) (0,3)
    (1,0) (1,1) (1,2) (1,3)
    (2,0) (2,1) (2,2) (2,3)
    We easily see that this is equivalent to laying these out in a single array:
    (0,0) (0,1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3)
    The column will always be 0, 1, 2, or 3 and the overflow will become the row. So if we have index 4 in the 1D array(so the 5th element), we have (4/4, 4%4) = (1, 0).

    def searchMatrix(self, matrix, target):
            """
            :type matrix: List[List[int]]
            :type target: int
            :rtype: bool
            """
            if len(matrix) == 0:
                return False
            left = 0
            right = len(matrix) * len(matrix[0]) - 1
            column = len(matrix[0])
            while left <= right:
                mid = (right + left)/2
                i = mid / column
                j = mid % column
                if (matrix[i][j] == target):
                    return True
                elif (matrix[i][j] < target):
                    left = mid + 1
                else:
                    right = mid - 1
            return False
    

Log in to reply
 

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