C# Concise Binary Search


  • 0
    M

    I essentially binary search for the intervals containing the start and end of the new interval, then compute the lower and upper indices of the intervals that should be merged if there is overlap with the interval being inserted. Then I copy the intervals before the group to be merged (the Take statement) insert the new interval, and then copy the remaining intervals into the result (the Skip statement). I use an implementation of Binary Search that returns either 1) the index of the interval containing the search value or 2) the bit-wise complement of the index directly after the location where the search value would properly be located in sorting order.

    public class Solution {
        public IList<Interval> Insert(IList<Interval> intervals, Interval newInterval) 
        {
            var retList = new List<Interval>(intervals.Count/2);
            int startInsertion = BinarySearch(intervals, newInterval.start);
            int endInsertion = BinarySearch(intervals, newInterval.end); 
            
    		int lowerInd = startInsertion < 0 ? ~startInsertion : startInsertion;
    		int upperInd = endInsertion < 0 ? (~endInsertion) : endInsertion + 1;
    		int newStart = startInsertion < 0 ? newInterval.start : intervals[lowerInd].start;
    		int newEnd = endInsertion < 0 ? newInterval.end : intervals[upperInd - 1].end;
    			
    		retList.AddRange(intervals.Take(lowerInd));
    		retList.Add(new Interval(newStart, newEnd));
    		retList.AddRange(intervals.Skip(upperInd));
    		
            return retList;
        }
        
        public static int BinarySearch(IList<Interval> list, int value)
        {
            int lower = 0;
            int upper = list.Count - 1;
            int mid = 0;
            
            while (lower <= upper)
            {
                mid = (lower + upper)/2;
                var midVal = list[mid];
                
                if (value < midVal.start)
                {
                    upper = mid - 1;
                } 
                else if (value > midVal.end)
                {
                    lower = mid + 1;
                }
                else
                {
                    return mid;
                }
            }
            
            return ~lower;
        }
    }
    

Log in to reply
 

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