How would I search a range of ranged values using C#

Question

I have a list of values like this

1000, 20400
22200, 24444

The ranges don't overlap.

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?

Does this make sense?

Need the quickest solution

Answer 1

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

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?

EDIT: 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.

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

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

Answer 2

A binary search will do just fine. Keep the list of ranges in sorted order, making sure that none of them intersect (if they do, merge them). Then write a binary search which, rather than testing against a single value, tests against either end of the range when looking to choose above or below.