c# - 我将如何使用 C# 搜索范围内的值

Question

我有一个这样的值列表

1000, 20400
22200, 24444

范围不重叠。

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

这有意义吗？

需要最快的解决方案

Answer 1

您已经指定了值，但随后谈到了范围。

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

编辑:通过对问题的编辑，Barry 的回答完全正确。只需在初始化时排序(按下界就足够了)，然后进行二进制搜索以找到包含该值或缺少该值的范围。

编辑:我在 my answer to a similar question 中找到了下面的代码最近。

范围需要事先排序 - 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;
}