对 DateTime 范围的二进制搜索

Question

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

我有一个查询，我想 return 处于特定范围内的 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 循环（你已经有了）中过滤结束时间。

对 DateTime 范围的二进制搜索

Binary search on DateTime ranges

c#

binary-search