log(N) for searching, but the step before return takes O(N):

```
def insert(self, intervals, newInterval):
[s,e] = newInterval.start, newInterval.end
s_floor = self.binary_search_floor(intervals, s)
e_floor = self.binary_search_floor(intervals, e)
if e_floor>=0: new_e = max(e, intervals[e_floor].end)
if s_floor == -1:
if e_floor==-1: #case: adding [1,2] into [[3,4]]
return [[s,e]]+intervals
return [[s,new_e]]+intervals[e_floor+1:] #case: adding [1,3] into [[2,4]]
elif s>intervals[s_floor].end: #case: adding [3,4] into [[1,2]]
return intervals[:s_floor+1]+[[s,new_e]]+intervals[e_floor+1:]
else:
new_s = intervals[s_floor].start #case: adding [3,5] into [[1,4]]
return intervals[:s_floor]+[[new_s,new_e]]+intervals[e_floor+1:]
def binary_search_floor(self, arr, t):
l,r = 0, len(arr)-1
ans = -1
while (l<=r):
mid = (l+r)/2
if arr[mid].start==t:
return mid
if arr[mid].start<t:
ans = mid
l = mid+1
else:
r = mid-1
return ans
```