# Easy to understand Python Binary Search Solution

• Modified based on the neat O(n) solution of Stefan.

``````# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
def insert(self, intervals, newInterval):
# log(n)
# find the largest index that interval i.end < s
def binarySearch1(intervals, s, l, r):
ret = -1
while l<=r:
mid = l+r >>1
if intervals[mid].end < s:
ret = mid
l=mid+1
else:
r=mid-1
return ret
# smallest i such that i.start > e
def binarySearch2(intervals, e, l, r):
ret = -1
while l<=r:
mid = l+r >>1
if intervals[mid].start > e:
ret = mid
r=mid-1
else:
l=mid+1
return ret
s = newInterval.start
e = newInterval.end
left = intervals[:binarySearch1(intervals, s, 0, len(intervals)-1)+1]
index_right = binarySearch2(intervals, e, 0, len(intervals)-1)
right = intervals[index_right:] if index_right != -1 else []
if len(left) + len(right) != len(intervals):
# megre
s = min(intervals[len(left)].start, s)
e = max(intervals[~len(right)].end, e)
return left + [Interval(s,e)] + right

``````

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