Coolcoder - 3 months ago 15

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

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