c# - 对 DateTime 范围的二进制搜索

Question

我有一个 TimeRange 对象的排序列表。每个 TimeRange 对象都有一个开始和结束 DateTime 对象。

我有一个查询，我想返回某个范围内的 TimeRange。我目前有一个如下所示的函数

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;
    }

这很慢，我想将 foreach 部分转换为二进制搜索(或任何其他合适的算法)，然后使用二进制搜索从原始列表复制到新列表，但我不确定如何进行这样做是因为我们在每个范围内都有开始和结束时间。任何帮助将不胜感激。

范围不重叠。例如范围 0 的结束时间总是小于范围 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 时，这应该比线性算法的表现要好得多。

注意:在创建用于搜索的虚拟 TimeRange 实例时，我使用了 new TimeRange(startTime, startTime) 这不是拼写错误。这是故意的。我们不关心那里的结束时间。我们在 for 循环(您已有)中过滤结束时间。