Python Binary Search O(logN), messy code


  • -1
    W
    class Solution(object):
        def insert(self, intervals, newInterval):
            """
            :type intervals: List[Interval]
            :type newInterval: Interval
            :rtype: List[Interval]
            """
            s, e = newInterval.start, newInterval.end
            a = self.binary_search(s, intervals)
            b = self.binary_search(e, intervals)
            if 0 <= a < len(intervals) and intervals[a].start <= s <= intervals[a].end:
                start = intervals[a].start
            else:
                start = s
            if 0 <= b < len(intervals) and intervals[b].start <= e <= intervals[b].end:
                end = intervals[b].end
                b += 1
            else:
                end = e
            return intervals[:a] + [Interval(start, end)] + intervals[b:]
            
            
            
        def binary_search(self, target, data):
            l, h = 0, len(data)-1
            while l <= h:
                mid = (l + h) / 2
                s, e = data[mid].start, data[mid].end
                if s <= target <= e:
                    return mid
                elif target < s:
                    h = mid - 1
                else:
                    l = mid + 1
            
            return l
    

Log in to reply
 

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