14 lines of python code using binary search

  • 0
    def searchMatrix(matrix, target):
        def search(lst, lo, hi, target):
            if hi - lo < 1:
                return False, lo-1 if 0 < lo <= len(lst) else None 
            mid = lo + (hi - lo)/2
            val = lst[mid] if isinstance(lst[mid], int) else lst[mid][0]
            if val == target:
                return True, mid
            elif val < target:
                return search(lst, mid+1, hi, target)
            return search(lst, lo, mid, target)
        found, idx = search(matrix, 0, len(matrix), target)
        return True if found else idx != None and search(matrix[idx], 0, len(matrix[idx]), target)[0]

    Hope this will help

Log in to reply

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