How to find if a list contains a key in Interval

Question

I have a sorted list of elements of <key,value>. The key is an unsigned int.

Is there any quick and efficient way in C# to determine if, given an interval , the list contains an element with a key in that interval?

Answer 1

If your list contains whole positive numbers, then you could build your own function very easily using LINQ Any, Enumerable.Range to create the range to check and List.Contains. The code can look like this:

var list = new List<int> { 1, 2, 3, 4, 5, 10, 100, 1000 };
// range to check
var min = 15;
var max = 18;
Console.WriteLine(list.Any (l => Enumerable.Range(min, max - min).ToList().Contains(l)) ? "Yes" : "No");

Output is for [15-18] No and for [9-11] Yes.

Another possibility (faster than the first one) is as @peter.petrov suggested to search in the given interval directly (using the LINQ where clause on the list):

var list = new List<int> { 1, 2, 3, 4, 5, 10, 100, 1000 };
// range to check
var min = 15;
var max = 18;
Console.WriteLine(list.Where (l => l > min && l < max).ToList().Count() > 0 ? "Yes" : "No");

Output is the same as in the first code example.

This approach can be applied to any class that implements the IEnumerable interface. One solution using a SortedList can look like this:

var list = new SortedList<int, int> { {1, 1}, {2, 2}, {3, 3}, {4, 10}, {5, 100} };
// range to check
var min = 15;
var max = 18;
Console.WriteLine(list.Where (l => l.Value > min && l.Value < max).ToList().Count () > 0 ? "Yes" : "No");

Answer 2

At first I missed the point that your list was sorted.

Seems possible, yes, in O(log N).

Suppose your interval is [A,B].
Let's say you have numbers C1, C2, ... CN in your
list and C[K] <= C[K+1] for each K.

1) Find the minimal K1 such that C[K1] >= A
If K1 is not found, answer is "not found"
2) Find the maximal K2 such that C[K2] <= B
If K2 is not found, answer is "not found"
3) Finally, if K1<=K2 answer is "found",
otherwise the answer is "not found".

For 1) and 2) you could use binary search, I think.
So all you need to do is to code this in C#.

Answer 3

SortedList has a method called ContainKey() which determines whether a SortedList object contains a specific key and is been internally determined using o(log N) since the underlined implementation is using a binary search tree. However in your case it is a range of Keys. So i recommend you to write a binary search on your range.

Answer 4

This will be the fastest solution because SortedList.ContainsKey implements Dictionary.ContainsKey and it is already an O(log n) operation. Also you can bail on the first match if you are only looking for membership.

SortedList<uint, int> n = new SortedList<uint, int>();

private bool KeyInRange(uint rangemin, uint rangemax;){
    for (uint i=rangemin; i<=rangemax; i++)
        if(n.ContainsKey(i))
            return true;

    return false;
}