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.

Answer 3

I'd try the simplest option first, and optimize if that doesn't meet your needs.

class Range {
   int Lower { get; set; }
   int Upper { get; set; }
}

List<Range>.FirstOrDefault(r => i >= r.Lower && i <= r.Upper);

Answer 4

Assuming your ranges don't overlap:

-> Put all your range numbers in an array.

-> Sort your array.

-> Also keep a HashSet for your startvalues.

-> Now do a binary search on your number. Two possiblities:

--> Array range left of (smaller then) your number is a start value: your number is in range.

--> Array range left of (smaller then) your number is not a start value: your number is not in range.

Answer 5

Is this functionally what you're after? If so, and you just want it to be more performant, than change the foreach in the ValueRangeCollection to a binary search..

    public struct ValueRange 
    { 
       public int LowVal; 
       public int HiVal; 
       public bool Contains (int CandidateValue) 
       { return CandidateValue >= LowVal && CandidateValue <= HiVal; } 
       public ValueRange(int loVal, int hiVal)
       {
          LowVal = loVal;
          HiVal = hiVal;
       }
   }

    public class ValueRangeCollection: SortedList<int, ValueRange> 
    { 
        public bool Contains(int candValue) 
        {  
            foreach ( ValueRange valRng in Values)
                if (valRng.Contains(candValue)) return true;
            return false; 
        }
        public void Add(int loValue, int hiValue)
        {
            Add(loValue, new ValueRange(loValue, hiValue));
        }
    }

Answer 6

class Range
{
   public int Start { get; set; }
   public int End { get; set; }

   static Dictionary<int, Range> values;
   static int[] arrToBinarySearchIn;
   public static void BuildRanges(IEnumerable<Range> ranges) { 
        values = new Dictionary<int, Range>();
        foreach (var item in ranges)
            values[item.Start] = item;
        arrToBinarySearchIn = values.Keys.ToArray();
        Array.Sort(arrToBinarySearchIn);
   }
   public static Range GetRange(int value)
   {
       int searchIndex = Array.BinarySearch(arrToBinarySearchIn, value);
       if (searchIndex < 0)
           searchIndex = ~searchIndex - 1;
       if (searchIndex < 0)
           return null;
       Range proposedRange = values[arrToBinarySearchIn[searchIndex]];
       if (proposedRange.End >= value)
           return proposedRange;
       return null;
   }
}

Answer 7

class Ranges
{
    int[] starts = new[] { 1000, 22200 };
    int[] ends = new[] { 20400, 24444 };

    public int RangeIndex(int test)
    {
        int index = -1;

        if (test >= starts[0] && test <= ends[ends.Length - 1])
        {
            index = Array.BinarySearch(ends, test);

            if (index <= 0)
            {
                index = ~index;
                if (starts[index] > test) index = -1;
            }
        }

        return index;
    }
}

Obviously, how you instantiate the class is up to you. Maybe pass in a DataTable and construct the arrays from that.