c# - 根据范围数据查找值

Question

什么数据结构或数据类型适合保存数据范围，并根据该范围内的数据返回一个值？

例如，假设我有以下范围

1-10 -> 1  
11-35 -> 2.5  
36-49-> 3.8  
50-60 -> 1.2  
61-80 -> 0.9 

在本例中，给定数字 41，我希望返回数字 3.8(因为 41 在 36 和 49 的范围之间)。

是否有一种巧妙的方法在数据结构中表示此类数据以执行此查找？

Answer 1

一个相对方便且非常高性能的实现是使用 SortedList<int, Tuple<int, double>> 。使用每个段的下界作为键，使用上限 + 映射值的元组作为值:

var list = new SortedList<int, Tuple<int, double>>
{
    { 1, Tuple.Create(10, 1.0) },
    { 11, Tuple.Create(35, 2.5) },
};

(当然，您可以决定使用更好看的数据结构来声明参数，以增强代码的可维护性，并在开始工作之前在内部转换为该结构)。

自 list.Keys保证已排序，查找值时可以使用 binary search在其上查找等于或大于您的输入值的索引:

var index = list.Keys.BinarySearch(value);
if (index < 0 && ~index == 0) {
    // no match, stop processing
}
else if (index < 0) {
    // key not found as is, look at the previous interval
    index = ~index - 1;
}

此时index点可能包含 value 的唯一范围，所以剩下的就是测试一下:

if(x >= list.Keys[index] && x <= list.Values[index].Item1) {
    var result = list.Values[index].Item2;
}
else {
    // no match
}

你不会称其为“干净”，但它非常短且非常快。