Java Binary Search in a List


  • 0
    D
    public class SummaryRanges {
        private List<Interval> intervals;
        /** Initialize your data structure here. */
        public SummaryRanges() {
            intervals = new ArrayList<>();
        }
        
        public void addNum(int val) {
            int idx = binarySearch(val);
            if (idx >= 0) {
                return;
            }
            
            idx = -idx - 1;
            if (idx == 0) {
                if (!intervals.isEmpty() && val + 1 == intervals.get(0).start) {
                    intervals.get(0).start = val;
                } else {
                    intervals.add(0, new Interval(val, val));
                }
            } else if (idx == intervals.size()) {
                if (intervals.get(idx - 1).end + 1 == val) {
                    intervals.get(idx - 1).end = val;
                } else {
                    intervals.add(new Interval(val, val));
                }
            } else {
                if (intervals.get(idx - 1).end + 2 == intervals.get(idx).start) {
                    intervals.get(idx - 1).end = intervals.get(idx).end;
                    intervals.remove(idx);
                } else if (intervals.get(idx - 1).end + 1 == val) {
                    intervals.get(idx - 1).end = val;
                } else if (intervals.get(idx).start - 1 == val) {
                    intervals.get(idx).start = val;
                } else {
                    intervals.add(idx, new Interval(val, val));
                }
            }
        }
        
        private int binarySearch(int val) {
            int left = 0, right = intervals.size();
            while (left < right) {
                int mid = left + (right - left) / 2;
                Interval curr = intervals.get(mid);
                if (val < curr.start) {
                    right = mid;
                } else if (val > curr.end) {
                    left = mid + 1;
                } else {
                    return mid;
                }
            }
            return -left - 1;
        }
        
        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.