根据范围数据查找值

Question

哪种数据结构或数据类型适合保存数据范围，并根据位于该范围内的数据返回值？

例如假设我有以下范围

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

在这种情况下给定的我希望数量3.8返回的数字41（如41 36至49的范围之间）。

在数据结构中表示这种数据是否有巧妙的方式来执行此查找？

Answer 1

您可以使用此代码

重点：

public class Interval<T> where T : IComparable 
{ 
    public Nullable<T> Start { get; set; } 
    public Nullable<T> End { get; set; } 

    public Interval(T start, T end) 
    { 
     Start = start; 
     End = end; 
    } 

    public bool InRange(T value) 
    { 
     return ((!Start.HasValue || value.CompareTo(Start.Value) > 0) && 
       (!End.HasValue || End.Value.CompareTo(value) > 0)); 
    } 
} 

值：小数

而且你可以使用此类型：Dictionary<Interval, decimal>

诺塔：您可以定义访问方法

Answer 2

一个比较方便和非常高效的impl ementation将使用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 
} 

你不会把这种“干净”，但它是非常短，速度非常快。

Answer 3

我花了一段时间，但我有一个QuickAndDirty方法，它假定所有给定的值是有效的，范围是相邻的，而不使用任何数据结构。 还有一个非常具体的数据结构，如果给定的索引恰好在指定的范围内，并且可以在运行时扩展，它将只返回一些内容。

public abstract class TreeNode 
{ 
    public static double QuickAndDirty(int index) 
    { 
     double result = 1.0; 

     if (index > 10) 
      result = 2.5; 

     if (index > 35) 
      result = 3.8; 

     if (index > 49) 
      result = 1.2; 

     if (index > 60) 
      result = 0.9; 

     return result; 
    } 

    public abstract double GetValue(int index); 

    public abstract TreeNode AddRange(int begin, int end, double value); 

    public static TreeNode MakeTreePart(Tuple<int, int, double>[] ranges) 
    { 
     return TreeNode.MakeTreePart(ranges, 0, ranges.Length >> 1, ranges.Length - 1); 
    } 

    private static TreeNode MakeTreePart(Tuple<int, int, double>[] ranges, int min, int index, int max) 
    { 
     if (index == min || index == max) 
      return new Leaf(ranges[index].Item1, ranges[index].Item2, ranges[index].Item3); 

     return new SegmentTree(
      ranges[index].Item2 + .5, 
      TreeNode.MakeTreePart(ranges, min, index >> 1, index - 1), 
      TreeNode.MakeTreePart(ranges, index + 1, index << 1, max)); 
    } 
} 

public class SegmentTree : TreeNode 
{ 
    private double pivot; 
    private TreeNode left, right; 

    public SegmentTree(double pivot, TreeNode left, TreeNode right) 
    { 
     this.pivot = pivot; 
     this.left = left; 
     this.right = right; 
    } 

    public override double GetValue(int index) 
    { 
     if (index < pivot) 
      return left.GetValue(index); 
     return right.GetValue(index); 
    } 

    public override TreeNode AddRange(int begin, int end, double value) 
    { 
     if (end < pivot) 
      this.left = this.left.AddRange(begin, end, value); 
     else 
      this.right = this.right.AddRange(begin, end, value); 
     // Do this to confirm to the interface. 
     return this; 
    } 
} 

public class Leaf : TreeNode 
{ 
    private int begin, end; 
    private double value; 

    public Leaf(int begin, int end, double value) 
    { 
     this.begin = begin; 
     this.end = end; 
     this.value = value; 
    } 

    public override double GetValue(int index) 
    { 
     if (index >= begin && index <= end) 
      return value; 
     throw new Exception("index out of range"); 
    } 

    public override TreeNode AddRange(int begin, int end, double value) 
    { 
     if (this.end < begin) 
      return new SegmentTree(((double)this.end + begin) * .5, this, new Leaf(begin, end, value)); 
     else if (end < this.begin) 
      return new SegmentTree(((double)end + this.begin) * .5, new Leaf(begin, end, value), this); 
     else throw new Exception("Indexes overlap."); 
    } 
} 
    static void Main() 
    { 
     TreeNode start = new Leaf(36, 49, 3.8); 
     start = start.AddRange(11, 35, 2.5); 
     start = start.AddRange(1, 10, 1.0); 
     start = start.AddRange(50, 60, 1.2); 
     start = start.AddRange(61, 80, 0.9); 
     double[] values = new double[70]; 
     for (int i = 1; i < values.Length; i++) 
      values[i] = start.GetValue(i); 

     TreeNode array = TreeNode.MakeTreePart(
      new Tuple<int, int, double>[] 
      { 
       Tuple.Create(1, 10, 1.0), 
       Tuple.Create(11, 35, 2.5), 
       Tuple.Create(36, 49, 3.8), 
       Tuple.Create(50, 60, 1.2), 
       Tuple.Create(61, 80, 0.9) 
      }); 

     for (int i = 1; i < values.Length; i++) 
      values[i] = start.GetValue(i); 
    }