# Binary search + (partial) linear scan, Pythonm beats 94.44% submissions

• ``````class Solution(object):

def binary_search(self, intervals, x, left, right):
if (left > right):
return None
mid = right - (right - left)/2
if ( intervals[mid].start <= x <= intervals[mid].end):
return mid
if (x < intervals[mid].start):
return self.binary_search(intervals, x, left, mid - 1)
else:
return self.binary_search(intervals, x, mid + 1, right)

def find_interval_that_contains(self, intervals, x):
return self.binary_search(intervals, x, 0, len(intervals) - 1)

def insert(self, intervals, newInterval):
"""
:type intervals: List[Interval]
:type newInterval: Interval
:rtype: List[Interval]
"""
if (len(intervals) == 0):
return [newInterval]

start_index = self.find_interval_that_contains(intervals, newInterval.start)
end_index = self.find_interval_that_contains(intervals, newInterval.end)
if (start_index is not None and end_index is None):

leftPart = intervals[0:start_index]
midPart = [Interval(s=intervals[start_index].start, e=newInterval.end)]
i = start_index
while(i < len(intervals) and intervals[i].start < newInterval.end):
i = i + 1
i = len(intervals) - 1 if i > len(intervals) else i
rightPart = intervals[i:]
return leftPart + midPart + rightPart

if (start_index is None and end_index is not None):
i = 0
while( i < len(intervals) and intervals[i].end < newInterval.start):
i = i + 1
leftPart = intervals[0:i]
midPart = [Interval(s=newInterval.start, e=intervals[end_index].end)]
rightPart = [] if end_index == len(intervals)-1 else intervals[end_index+1:]
return leftPart + midPart + rightPart

if (start_index is None and end_index is None):
i = 0
while(i < len(intervals) and intervals[i].start < newInterval.start):
i = i + 1
leftPart = intervals[0:i]
while(i < len(intervals) and intervals[i].start < newInterval.end):
i = i + 1

midPart = [newInterval]
rightPart = intervals[i:]
return leftPart + midPart + rightPart

intervals[start_index].end = intervals[end_index].end
del intervals[start_index+1:end_index+1]
return intervals
``````

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