Java binary search with explanation about the if-else


  • 0
    Y
    public class SummaryRanges {
    
    	List<Interval> intervals;
    
        public SummaryRanges() {
        	intervals = new ArrayList<Interval>();
        }
        
        public void addNum(int val) {
        	int pos = binarySearch(val);
    
            if (pos < 0) {
                'not found, so we should add new or insert at first'
                if (intervals.size() > 0 && val == intervals.get(0).start - 1) {
                    intervals.get(0).start = val;
                } else {
                    intervals.add(0, new Interval(val, val));
                }
            } else {
                'since we use end position, now check if should just modify someInterval.end or add new (then check merge)'
                if(val == intervals.get(pos).end + 1) {
                    intervals.get(pos).end = val;
                } else if (val > intervals.get(pos).end + 1) {
                    intervals.add(pos + 1, new Interval(val, val));
                    pos++;
                }
                'check if needs merge'
                if (pos + 1 < intervals.size() && intervals.get(pos).end + 1 == intervals.get(pos + 1).start) {
                    intervals.get(pos).end = intervals.get(pos + 1).end;
                    intervals.remove(pos + 1);
                }
            }    
        }
    
        public int binarySearch(int n) {
        	int start = 0;
        	int end = intervals.size() - 1;
            int mid = 0;
            if (end < 0) {
                return -1;
            }
        	while(start <= end) {
        		mid = (end - start) / 2 + start;
        		if (n < intervals.get(mid).start) {
        			end = mid - 1;
        		} else {
        			start = mid + 1;
        		}
        	}
        	return end;
        }
        
        public List<Interval> getIntervals() {
            return intervals;
        }
    }

Log in to reply
 

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