c# - 散列范围

Question

我有一个范围元素数组。每个元素都有开始和结束。在数组中，范围不重叠，并且它们是排序的。

即(代码只是为了说明，不要指望它能编译):

var arr = { [0,3], [5,10], [15,59] };

给定一个值(比如 9)，是否有一个范围的哈希函数可以让我快速获取具有包含该值的范围的元素？

当然有一个简单的解决方案，就是循环遍历每个元素，直到找到正确的那个；更复杂的一个，比如从范围开始的二进制搜索；以及创建具有范围的二叉树的专利之一。

但是有人知道使用哈希的方法吗？

Answer 1

您可以预先计算最近的邻居并将其存储在某个地方。在您的示例中，该表有 0..59 个条目，您将最近范围的索引存储在每个索引处。

这样它会非常快。