Clever Geek Handbook

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

I have Dictionary<int,string>

with ascending keys:

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 less than my value. In this case, I need to return 2500.

I tried:

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

}

But, as you might expect, all lower values ​​also coincide.

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

+3


source to share


4 answers


Using LinQ is the easiest way:



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


source


You can create List<int>

from the keys a dictionary. I would keep this list if you need to search for it often. Then you can use List.BinarySearch

to find the closest 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 index of the element in the sorted List<T>

one if the element is found; otherwise, a negative number that is the bit's complement to the index of the next element greater than the element, or, if there is no larger element, the bit's complement to Count.

+1


source


Giorgos answer is the best way to work with Dictionary

, but it will be slow because it will search the entire keyspace. If you want something fast, the C5 Collections library has a lot of features not found in .NET. You can do it:

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

which will run in O (log n), much more efficient as your vocabulary grows.

+1


source


You can use an integer to keep track of the highest value.

int temp = 0;
foreach (var key in myDictionary.Keys)
{
    if (key > temp) { temp = key; }
}
if (searchvalue > temp) { // invalidate search}
//Do something with temp here.
0


source






More articles:


All Articles