A Python binary search solution - O(logn)


  • 16
    G

    It is basically an advanced version of the binary search

    class Solution:
        # @param matrix, a list of lists of integers
        # @param target, an integer
        # @return a boolean
        # 8:21
        def searchMatrix(self, matrix, target):
            if not matrix or target is None:
                return False
    
            rows, cols = len(matrix), len(matrix[0])
            low, high = 0, rows * cols - 1
            
            while low <= high:
                mid = (low + high) / 2
                num = matrix[mid / cols][mid % cols]
    
                if num == target:
                    return True
                elif num < target:
                    low = mid + 1
                else:
                    high = mid - 1
            
            return False

  • 1
    I

    This is brilliant !!


  • 9
    C

    Strictly, I think this is O(logmn)


  • 2

    Another solution. small difference in checking boundary

    class Solution(object):
        def searchMatrix(self, matrix, target):
            """
            :type matrix: List[List[int]]
            :type target: int
            :rtype: bool
            """
            if not matrix or not matrix[0]:
                return False
    
            l, r = 0, len(matrix)*len(matrix[0])
    
            while l<r:
                mid = (l+r)//2
                i, j = mid//len(matrix[0]), mid%len(matrix[0])
                if matrix[i][j]==target:
                    return True
                elif matrix[i][j]>target:
                    r = mid
                else:
                    l = mid + 1
        
            return False
    

  • 0
    Y
    This post is deleted!

  • 1
    W

    gj.And here is my solution, beat 100% and I think it is easy to understand

    if not matrix or not matrix[0]: return False
            for i in range(len(matrix)):
                if target==matrix[i][-1]: return True
                elif target<matrix[i][-1]:
                    for j in range(len(matrix[0])):
                        if matrix[i][j]==target: return True
                    return False
            return False
    

Log in to reply
 

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