如何使用C#搜索一系列范围值

Question

我有一个像这样的值列表

1000, 20400
22200, 24444

范围不重叠.

我想要做的是拥有可以存储的ac#函数(从db加载的值然后在本地缓存它)这些值的相对较大的列表然后有一个方法来查找提供的值是否在任何范围内？

这有意义吗？

需要最快的解决方案

Answer 1

你已经指定了值,但随后谈到了范围.

对于正义值,我会使用HashSet<int>.对于范围来说它变得更加复杂......让我们知道这实际上是你所追求的,我会更多地考虑它.如果它们是范围,您是否有关于它们的任何额外信息？你知道他们是否会重叠吗？您是否只对范围的存在感兴趣,还是需要找到值所属的所有范围？

编辑:通过对问题的编辑,巴里的答案是完全正确的.只是在初始化时排序(通过下限足够好)然后进行二分查找以找到包含该值的范围,或者缺少该值.

编辑:我最近在回答类似问题时找到了以下代码.

范围将需要预先排序 - List<Range>.Sort假设您没有重叠,将正常工作.

public class Range : IComparable<Range>
{
      private readonly int bottom; // Add properties for these if you want
      private readonly int top;

      public Range(int bottom, int top)
      {
             this.bottom = bottom;
             this.top = top;
      }

      public int CompareTo(Range other)
      {
             if (bottom < other.bottom && top < other.top)
             {
                   return -1;
             }
             if (bottom > other.bottom && top > other.top)
             {
                   return 1;
             }
             if (bottom == other.bottom && top == other.top)
             {
                   return 0;
             }
             throw new ArgumentException("Incomparable values (overlapping)");
      }

      /// <summary>
      /// Returns 0 if value is in the specified range;
      /// less than 0 if value is above the range;
      /// greater than 0 if value is below the range.
      /// </summary>
      public int CompareTo(int value)
      {
             if (value < bottom)
             {
                   return 1;
             }
             if (value > top)
             {
                   return -1;
             }
             return 0;
      }
}

// Just an existence search
public static bool BinarySearch(IList<Range> ranges, int value)
{
    int min = 0;
    int max = ranges.Count-1;

    while (min <= max)
    {
        int mid = (min + max) / 2;
        int comparison = ranges[mid].CompareTo(value);
        if (comparison == 0)
        {
            return true;
        }
        if (comparison < 0)
        {
            min = mid+1;
        }
        else if (comparison > 0)
        {
            max = mid-1;
        }
    }
    return false;
}

Answer 2

二分搜索就可以了.按排序顺序保留范围列表,确保它们都不相交(如果相同,则合并它们).然后编写一个二进制搜索,而不是针对单个值进行测试,在查看上方或下方时,针对范围的任一端进行测试.