Python Binary Search beats 97%


  • 0
    def insert(self, intervals, newInterval):
        start = self.search_intervals(intervals, newInterval.start, "search start")
        end = self.search_intervals(intervals, newInterval.end, "search end")
        
        if start > 0 and intervals[start - 1].end >= newInterval.start:
            start -= 1
        if end == len(intervals) or intervals[end].start > newInterval.end:
            end -= 1
        if start <= end:
            newInterval.start = min(intervals[start].start, newInterval.start)
            newInterval.end = max(intervals[end].end, newInterval.end)
        return intervals[:start] + [newInterval] + intervals[end + 1:]
    
    def search_intervals(self, intervals, val, flag):
        left, right = 0, len(intervals) - 1
        while left <= right:
            mid = (left + right) / 2
            if flag == "search start":
                mid_val = intervals[mid].start
            elif flag == "search end":
                mid_val = intervals[mid].end
            if mid_val == val:
                return mid
            elif mid_val < val:
                left = mid + 1
            else:
                right = mid - 1
        return left

Log in to reply
 

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