Doing a range lookup in C#?

Question

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?

Answer 1

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 :)