CODEWITHSUNDEEP
c#
Waleed Eissa
Waleed Eissa

Reputation: 10513

Doing a range lookup in C#?

I have a list of non-overlaping ranges (ranges of numbers, e.g. 500-1000, 1001-1200 .. etc), is there an elegant and fast way to do lookup by only passing a number? I could use List.BinarySearch() or Array.BinarySearch() but I have to pass the type of the range object (Array.BinarySearch(T[], T)), I can pass a dummy range object and get the job done (only do the comparison with the range start) but I was wondering if this can be done in a cleaner way by only passing an integer and getting the range object, is there a way to achieve this?

Upvotes: 6

Views: 4971

Answers (3)

Jon Skeet
Jon Skeet

Reputation: 1500665

Three options:

  • Create a dummy Range and suck it up. Urgh.
  • Hand-craft a binary search just for this case. Not too bad.
  • Generalise the binary search for any IList and a TValue, given an IRangeComparer. I'm not wild on the name "TRange" here - we're not necessarily talking about ranges, but just finding the right place based on a comparison between two different types.

The third option would go something like:

public interface IRangeComparer<TRange, TValue>
{
    /// <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>
    int Compare(TRange range, TValue value);
}


/// <summary>
/// See contract for Array.BinarySearch
/// </summary>
public static int BinarySearch<TRange, TValue>(IList<TRange> ranges,
                                               TValue value,
                                               IRangeComparer<TRange, TValue> comparer)
{
    int min = 0;
    int max = ranges.Count-1;

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

Apologies if I've got any off-by-one errors. I haven't tested it at all, but it does at least compile :)

Upvotes: 14

PerryJ
PerryJ

Reputation: 399

If you have lots of ranges and are really concerned about performance you could create an AVL type of tree consisting of the range(min,max) pairs, but sorted on the lowest part of the range.

However, if you don't have a lot of ranges to sort things into, this is a lot of work for virtually no gain.

Upvotes: 1

Ria
Ria

Reputation: 364

If you have .Net 3.5 or above, try

foundRange = yourList.Where(range =› range.BottomNumber ‹= searchInt && range.TopNumber ›= searchInt).FirstOrDefault();

Upvotes: 1

Related Questions