How do I find next largest key in a collection?

Question

Suppose I have a dictionary in C#. Assuming the keys are comparable, how do I find the smallest key greater than a given k (of the same type as the keys of the dictionary)? However I would like to do this efficiently with a collection like a SortedDictionary.

Clearly, if it were not a question of doing it efficiently one could start with any dictionary, extract its keys and then use the First method with a suitable predicate. But this would execute in linear time (in the number of keys) when if one has a sorted set of keys one should be be able to find the key in log time.

Thanks.

Answer 1

The SortedList<TKey, TValue> class implements IDictionary<TKey, TValue> and has an IndexOfKey method; I think that's what you want:

// I'm just going to pretend your keys are ints
var collection = new SortedList<int, string>();

// populate collection with whatever

int k = GetK(); // or whatever

int kIndex = collection.IndexOfKey(k);

int? smallestKeyGreaterThanK = null;
if (collection.Count > kIndex + 1)
    smallestKeyGreaterThanK = collection.Keys[kIndex + 1];

According to the MSDN documentation:

This method performs a binary search; therefore, this method is an O(log n) operation.

EDIT: If you can't be sure that the dictionary contains the key you're looking for (you just want the next-largest), there is still a way to leverage an existing binary search method from .NET for your purposes. You said you are looking for an "efficient" solution; the following fits that criterion if you mean in terms of your time (and in terms of lines of code). If you mean in terms of memory usage or performance, on the other hand, it might not be ideal. Anyway:

List<int> keysList = new List<int>(collection.Keys);
int kIndex = keysList.BinarySearch(k);

Now, BinarySearch will give you what you're looking for, but if the key's not there, it's a little wacky. The return value, from the MSDN documentation, is as follows:

The zero-based index of item in the sorted List<T>, if item is found; otherwise, a negative number that is the bitwise complement of the index of the next element that is larger than item or, if there is no larger element, the bitwise complement of Count.

What this means is that you'll need to add another line:

kIndex = kIndex >= 0 ? kIndex : ~kIndex;