Binary Search in DateTime Ranges

Question

I have a sorted list of objects TimeRange. Each object TimeRangehas an object of beginning and end DateTime.

I have a query in which I would like to return TimeRangewhich fall between a certain range. I currently have a function that looks like this

protected List<TimeRange> GetBoundedTimeRanges(List<TimeRange> timeRanges, DateTime startTime,
        DateTime endTime)
    {
        if (timeRanges == null || timeRanges.Count == 0)
        {
            return null;
        }

        var ranges = new List<TimeRange>();

        foreach (var range in timeRanges)
        {
            // If the end of the range is before the start time
            if (range.End < startTime)
            {
                continue;
            }

            // If the start of the range is after the end time
            // then break. 
            if (range.Start > endTime)
            {
                break;
            }

            // Otherwise the value falls between the range
            ranges.Add(range);
        }

        return ranges;
    }

This is pretty slow, and I would like to convert the foreach part to a binary search (or any other suitable algorithm) and then copy from the original list to a new list using binary search, however I'm not sure how to do this since we have time start and end in each range. Any help would be appreciated.

Ranges do not overlap. For example, the end time of range 0 is always less than the start time of range 1

Range found - Start Time 03/02/2015 22:51:50, End Time 10/03/2015 15:44:56
Range found - Start Time 10/03/2015 15:46:26, End Time 11/03/2015 08:38:56
Range found - Start Time 11/03/2015 08:43:12, End Time 13/03/2015 04:15:05
Range found - Start Time 13/03/2015 04:15:08, End Time 17/03/2015 13:38:21
Range found - Start Time 17/03/2015 13:40:00, End Time 17/03/2015 15:15:52
Range found - Start Time 17/03/2015 15:19:05, End Time 17/03/2015 15:20:42
Range found - Start Time 17/03/2015 15:39:48, End Time 24/03/2015 16:37:29
Range found - Start Time 24/03/2015 16:42:25, End Time 25/03/2015 07:46:54
Range found - Start Time 25/03/2015 07:50:23, End Time 25/03/2015 15:36:33
Range found - Start Time 25/03/2015 15:40:15, End Time 25/03/2015 15:48:44
Range found - Start Time 25/03/2015 15:52:40, End Time 25/03/2015 15:57:21
Range found - Start Time 25/03/2015 16:01:22, End Time 31/03/2015 09:18:49
Range found - Start Time 31/03/2015 09:22:12, End Time 01/04/2015 10:00:26

Answer 1

. , , .

protected List<TimeRange> GetBoundedTimeRanges(List<TimeRange> timeRanges, DateTime startTime, DateTime endTime)
{
    var startSearch = timeRanges.BinarySearch(new TimeRange(startTime, startTime), new TimeRangeComparer());
    if (startSearch < 0)
    {
        startSearch = ~startSearch;
    }

    var ranges = new List<TimeRange>();
    for (int i = startSearch; i < timeRanges.Count; i++)
    {
        var range = timeRanges[i];
        if (range.End < startTime)
        {
            continue;
        }
        if (range.Start > endTime)
        {
            break;
        }
        ranges.Add(range);
    }

    return ranges;
}

class TimeRangeComparer : IComparer<TimeRange>
{
    public int Compare(TimeRange x, TimeRange y)
    {
        var startResult = x.End.CompareTo(y.Start);
        if (startResult != 0)
        {
            return startResult;
        }

        return x.End.CompareTo(y.End);
    }
}

, , BinarySearch.

. dummy TimeRange new TimeRange(startTime, startTime), . . . for ( ).