Find largest Dictionary<int,string> key whose value is less than the search value

Question

I have Dictionary<int,string> with ascending keys like this:

var myDictionary = new Dictionary<int,string>
{
    {750,"one"},
    {1500,"two"},
    {2500,"three"},
    {5000,"four"},
    {10000,"five"},
    {25000,"six"}
}

I have var myValue = 3000.52

I need to find the largest myDictionary key that is smaller than my value. In this case, I need to return 2500.

I have tried:

foreach (var key in myDictionary.Keys.Where(key => key <= myValue))
{

}

But, as you would expect, all smaller values also match.

How do I find the largest key that is smaller than my search value?

Answer 1

Using LinQ is the simplest way I think:

int myKey = myDictionary.Where(x => x.Key < myValue)
                        .OrderByDescending(x => x.Key)
                        .First().Key;

Answer 2

You could create a List<int> from the dictionary keys. I would store this list if you need to lookup it often. Then you can use List.BinarySearch to find the nearest key:

int key = 3000;
var keys = new List<int>(myDictionary.Keys);
// keys.Sort(); if it was not already sorted
var index = keys.BinarySearch(key);
if (index >= 0)
{
    // dictionary contains this key
}
else
{
    int nextSmaller = ~index - 1;
    string valueOfNextSmaller = myDictionary[keys[nextSmaller]]; // three
}

BinarySearch returns 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.

Answer 3

Giorgos' answer is the best you'll be able to do working with Dictionary, but it will be slow because this will search the entire keyspace. If you want something fast, the C5 collections library has a lot of features lacking in .NET. You can do this:

TreeDictionary<K,V> dict;
var last = dict.RangeTo(myValue).Backwards().First();

Which will execute in O(log n), much more efficient as your dictionary's size grows.