使用C＃如何将搜索范围的范围值 [英] How would I search a range of ranged values using C#

问题描述

我有值的像这样的列表

1000, 20400
22200, 24444

的范围不重叠。

The ranges don't overlap.

我想要做的是有一个C＃的功能，可以存储（从数据库，然后缓存在本地加载的值），这些值的比较大的名单，然后对发现，如果提供的值是在任何范围的方法？

What I want to do is have a c# function that can store (loaded values from db then cache it locally) a relatively large list of these values then have a method for finding if a supplied value is in any of the ranges?

这是否有道理？

需要最快的解决办法

推荐答案

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

You've specified values, but then talked about ranges.

有关正义价值观，我会使用一个的HashSet＆LT; INT＆GT; 。对于范围，它变得更加复杂......让我们知道，经过实际上你是什么，我会考虑的更多。如果他们的是的范围内，你有没有关于他们的任何额外信息？你知不知道他们是否会重叠或不？你是在一个范围内的存在只是有兴趣，或者你需要找到所有范围的值属于？

For just values, I'd use a HashSet<int>. For ranges it gets more complicated... Let us know if that's actually what you're after and I'll think about it more. If they are ranges, do you have any extra information about them? Do you know if they'll overlap or not? Are you just interested in the existence of a range, or do you need to find all the ranges that a value belongs to?

编辑：随着编辑的问题，巴里的回答是完全正确的。只是排序（按下限是不够好）在初始化时，然后做一个二进制搜索，找到包含该值的范围内，或缺乏。

With the edits to the question, Barry's answer is exactly right. Just sort (by lower bound is good enough) at initialization time and then do a binary search to find the range containing the value, or the lack thereof.

编辑：我已经找到了code低于我的回答最近类似的问题

I've found the code below in my answer to a similar question recently.

的范围将需要预先排序 - 名单，LT;范围和GT; .Sort 将正常工作，假设你有没有重叠

The ranges will need to be sorted beforehand - List<Range>.Sort will work fine assuming you have no overlap.

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;
}

这篇关于使用C＃如何将搜索范围的范围值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！