# Java Binary Search O(logn) Solution

• The following is the solution using binary search. I code it for easy to understand without optimization. Hope it can help.

``````public class Solution {
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
if(intervals.size()==0){
return intervals;
}
int l=0;
int r=intervals.size()-1;
int startInsertIndex=0;
boolean startIntersect=false;
int endInsertIndex=intervals.size()-1;
boolean endIntersect=false;

// Below logic to do the binary search, if the intersection found, the index will end at exact place.
// if the intersection not found, the index is at the insert position.
// sample:  [3,5], [7,9],[12,14]      insert[1,6] then:  startIntersect=0, endInsertIndex=1
// index:   0      1     2
while(l<=r){
int mid=(r-l)/2+l;
startInsertIndex=mid;
if(intervals.get(mid).start>newInterval.start){
//search left side
r=mid-1;
}else if(intervals.get(mid).end<newInterval.start){
//search right side
l=mid+1;
}else if(intervals.get(mid).start<=newInterval.start && intervals.get(mid).end>=newInterval.start){
//found the intercept interval
startIntersect=true;
startInsertIndex=mid;
break;
}
}
if(startIntersect==false && intervals.get(startInsertIndex).end<newInterval.start){
startInsertIndex++;
}
l=startInsertIndex; //this intersection can be at the same interval, so search from startInsertIndex to the end
r=intervals.size()-1;
while(l<=r){
int mid=(r-l)/2+l;
endInsertIndex=mid;
if(intervals.get(mid).start>newInterval.end){
//search left side
r=mid-1;
}else if(intervals.get(mid).end<newInterval.end){
//search right side
l=mid+1;
}else if(intervals.get(mid).start<=newInterval.end && intervals.get(mid).end>=newInterval.end){
//found the intercept interval
endIntersect=true;
endInsertIndex=mid;
break;
}
}
if(endIntersect==false && intervals.get(endInsertIndex).end<newInterval.end){
endInsertIndex++;
}

//System.out.println(startInsertIndex + ", " +endInsertIndex);
if(startIntersect && endIntersect){
Interval a_new = new Interval(intervals.get(startInsertIndex).start, intervals.get(endInsertIndex).end);
for(int i=0; i<=(endInsertIndex-startInsertIndex); i++){
intervals.remove(startInsertIndex);
}
return intervals;
}else if(startIntersect){
Interval a_new = new Interval(intervals.get(startInsertIndex).start, newInterval.end);

//meger all the interval in the middle, which means delete them
if(startInsertIndex==endInsertIndex){
//remove one;
intervals.remove(endInsertIndex);
}else{
for(int i=0; i<(endInsertIndex-startInsertIndex); i++){
intervals.remove(startInsertIndex);
}
}
return intervals;
}else if(endIntersect){
Interval a_new = new Interval(newInterval.start, intervals.get(endInsertIndex).end);

//meger all the interval in the middle, which means delete them
if(startInsertIndex==endInsertIndex){
//remove one;
intervals.remove(endInsertIndex);
}else{
for(int i=0; i<=(endInsertIndex-startInsertIndex); i++){
intervals.remove(startInsertIndex);
}
}
return intervals;
}else{
//both start and end doesn't have intersection
if(startInsertIndex==endInsertIndex){
//no need to merge any interval
return intervals;
}

//meger all the interval in the middle, which means delete them
for(int i=0; i<(endInsertIndex-startInsertIndex); i++){
intervals.remove(startInsertIndex);
}