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?

This is going to be very dependant on what version of .Net – Tom Anderson Jan 17 '09 at 23:00 — Tom Anderson, Jan 17 '09 at 23:00

Jon Skeet · Accepted Answer · 2009-01-18T07:55:03.800

13

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

edited Jan 18 '09 at 07:55

answered Jan 17 '09 at 23:40

Jon Skeet

1,421,763
867
9,128
9,194

Thanks a lot, I'm going to use your code. One little thing though, Compare() should return less than 0 if value is above the range and vice versa. – Waleed Eissa Jan 18 '09 at 01:30
If you are going to use his code, shouldn't you accept it as the answer – Alex Jan 18 '09 at 02:21
Fixed doc comment for IRangeComparer. – Jon Skeet Jan 18 '09 at 07:55
For reference: I’ve written a functional implementation of the above code for `IComparable` values at [Doing a range lookup in C# - how to implement](http://stackoverflow.com/questions/8948205/doing-a-range-lookup-in-c-sharp-how-to-implement/8949322#8949322). – Douglas Jan 20 '12 at 23:48
Isn't there a built-in .NET class by now that could be used for this purpose? I see we have `SortedList`, but I don't need a value to go along with my ranges. – Jonathan Wood Sep 23 '16 at 15:48
@JonathanWood: I don't know of anything, no. – Jon Skeet Sep 23 '16 at 15:49

score 1 · Answer 2 · answered Jan 17 '09 at 23:30

1

If you have .Net 3.5 or above, try

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

answered Jan 17 '09 at 23:30

Ria

364
4
8

5

That's going to be O(n) - it'll work, but I think we can do better :) – Jon Skeet Jan 17 '09 at 23:31

score 1 · Answer 3 · answered Jan 18 '09 at 02:07

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.

Doing a range lookup in C#?

3 Answers3

Linked

Related