A Python binary search solution - O(logn)


  • 0
    G

    we can ignore the matrix because we can simply convert it to a sorted linear array!

    class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        m = len(matrix)
        n = len(matrix[0])
        
        xl = 0
        xr = m*n-1
        
        while (True):
            xm = (xl+xr)/2
            if (matrix[xm/n][xm%n] == target):
                return True
            if (xl >= xr):
                return False
            if (matrix[xm/n][xm%n] > target):
                xr = xm-1
            else:
                xl = xm+1

Log in to reply
 

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