# Clean Binary Search Solution

• ``````class Solution {
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {

List<Interval> res = new ArrayList<Interval>();
int n = intervals.size();

// find the position of the first overlapping element of intervals with newInterval
int i = findFirstOverlappingPos(intervals, newInterval);
// add the elements of intervals that are before the first overlapping position to res
for(int j = 0; j < i; j++) {
}

// merge overlapped elements of intervals with newInterval
if(i < n) {
newInterval.start = Math.min(intervals.get(i).start, newInterval.start);
}
// find the position of the last overlapping element of intervals with newInterval
i = findLastOverlappingPos(intervals, newInterval, i);
if(i >= 0) {
newInterval.end = Math.max(intervals.get(i).end, newInterval.end);
}

// add the elements of intervals that are after the first overlapping position to res
for(i = i + 1; i < n; i++) {
}

return res;
}

public int findLastOverlappingPos(List<Interval> intervals, Interval newInterval, int l) {

int origL = l;

int r = intervals.size() - 1;

while(l <= r) {
int m = l + (r - l)/2;
if(intervals.get(m).start <= newInterval.end) {
if(m == (intervals.size() - 1) ||
intervals.get(m + 1).start > newInterval.end) {
return m;
} else {
l = m + 1;
}
} else {
r = m - 1;
}
}

return origL - 1;
}

public int findFirstOverlappingPos(List<Interval> intervals, Interval newInterval) {

int origR = intervals.size() - 1;

int l = 0;
int r = origR;

while(l <= r) {
int m = l + (r - l)/2;
if(newInterval.start <= intervals.get(m).end) {
if(m == 0 || intervals.get(m - 1).end < newInterval.start) {
return m;
} else {
r = m - 1;
}
} else {
l = m + 1;
}
}

return origR + 1;
}
}
``````

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