Python: O(log n + log m) solution considering the matrix as a single array


  • 0
    G

    Given that each row is sorted and "the first integer of each row is greater than the last integer of the previous row", then we have that this matrix:

    [
      [1,   3,  5,  7],
      [10, 11, 16, 20],
      [23, 30, 34, 50]
    ]
    

    is identical to this array:

    [1, 3, 5, 7] + [10, 11, 16, 20] + [23, 30, 34, 50]
    

    Therefore we can use the "standard" binary search algorithm:

    class Solution(object):
        def searchMatrix(self, matrix, target):
            rows = len(matrix)
            cols = len(matrix[0])
            items = rows * cols
            
            low = 0
            high = items - 1
            
            while high >= low:
                k = (high + low) // 2
                i, j = divmod(k, cols)
                v = matrix[i][j]
                
                if v < target:
                    low = k + 1
                elif v > target:
                    high = k - 1
                else:
                    return True
            
            return False

Log in to reply
 

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