搜索范围列表中数字的最快方法
我有以下代码来查找范围列表中的数字匹配。
public class RangeGroup { public uint RangeGroupId { get; set; } public uint Low { get; set; } public uint High { get; set; } // More properties related with the range here } public class RangeGroupFinder { private static readonly List RangeGroups=new List(); static RangeGroupFinder() { // Populating the list items here RangeGroups.Add(new RangeGroup { RangeGroupId = 0, Low = 1023238144, High = 1023246335 }); RangeGroups.Add(new RangeGroup { RangeGroupId = 0, Low = 1023246336, High = 1023279103 }); RangeGroups.Add(new RangeGroup { RangeGroupId = 0, Low = 1023279104, High = 1023311871 }); RangeGroups.Add(new RangeGroup { RangeGroupId = 0, Low = 1023311872, High = 1023328255 }); RangeGroups.Add(new RangeGroup { RangeGroupId = 0, Low = 1023328256, High = 1023344639 }); RangeGroups.Add(new RangeGroup { RangeGroupId = 0, Low = 1023344640, High = 1023410175 }); RangeGroups.Add(new RangeGroup { RangeGroupId = 0, Low = 1023410176, High = 1023672319 }); RangeGroups.Add(new RangeGroup { RangeGroupId = 0, Low = 1023672320, High = 1023688703 }); RangeGroups.Add(new RangeGroup { RangeGroupId = 0, Low = 1023692800, High = 1023696895 }); // There are many more and the groups are not sequential as it can seen on last 2 groups } public static RangeGroup Find(uint number) { return RangeGroups.FirstOrDefault(rg => number >= rg.Low && number <= rg.High); } } RangeGroup的列表包含大约5000000个项目，并且Find（）方法将被大量使用，因此我正在寻找一种更快的方式来进行搜索。 更改数据结构或以任何方式拆分数据都没有问题。
编辑：
所有范围都是唯一的，并按低的顺序添加，它们不重叠。
结果：
使用ikh的代码进行测试，结果比我的代码快大约7000倍。 测试代码和结果可以在这里看到。
由于您指示RangeGroup是按RangeGroup.Low顺序添加的，并且它们不重叠，因此您无需进行任何进一步的预处理。 您可以在RangeGroups列表上进行二进制搜索以查找范围（警告：未完全测试，您需要检查一些边缘条件）：
public static RangeGroup Find(uint number) { int position = RangeGroups.Count / 2; int stepSize = position / 2; while (true) { if (stepSize == 0) { // Couldn't find it. return null; } if (RangeGroups[position].High < number) { // Search down. position -= stepSize; } else if (RangeGroups[position].Low > number) { // Search up. position += stepSize; } else { // Found it! return RangeGroups[position]; } stepSize /= 2; } }
最坏情况下的运行时间应该在O（log（N））附近，其中N是RangeGroup的数量。
间隔树。 是为了满足你的要求而精心设计的。
如果只填充列表一次，你可以做一个魔术：
- 对列表排序
- 使用BinarySearch
排序需要O（Nlog（N））时间并且只执行一次。 二进制搜索需要O（log（N）），最多需要17个比较100,000个项目。
可以使用排序列表并进行二分查找。 这样你可以减少与O（logN）的比较次数
在两个不同的数组中对范围进行两次排序。 一旦通过该范围中的最小值，一次在该范围内的最大值。 然后执行两次二进制搜索，保存与任一约束匹配的范围。 最后，做两组可能性的集合交集。