在日期时间范围内进行二分查找

Question

在日期时间范围内进行二分查找

4

我有一个按照时间顺序排列的 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

- const_ref

2

你的时间范围是否有序？如果是无序的，那么我不确定你能做得比仅查看每个时间范围并检查其是否正确更好。如果它们是有序的，那么确切的算法将取决于它们的排序方式（例如按开始日期、结束日期或更复杂的中点等）。 - Chris

范围是否重叠或者是不重叠的？ - Sriram Sakthivel

1

范围不重叠。范围0的结束时间始终小于范围1的开始时间。 - const_ref

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sriram Sakthivel · Accepted Answer

如果您的列表按开始时间排序。您可以使用自定义比较器运行二进制搜索，以找出可能位于哪个范围内。

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

我们使用二分搜索，因此这应该比线性算法表现更好。

注意：在创建用于搜索的虚拟 TimeRange 实例时，我使用了 new TimeRange(startTime, startTime)，这不是打字错误，而是有意为之。我们不关心结束时间，因为您已经在 for 循环中过滤了结束时间。