How to get the nearest key to a specified number in a dictionary?

Question

I have an Excel function which I'm trying to translate to C# equivalent code. The function (in Excel) is as follows:

WorksheetFunction.VLookup(number, Range("numberDictionary"), 2, True)

Essentially what this function does is...

Assuming a dictionary exists, defined as follows:

Number | Value
1      | 2
3      | 8
9      | 1

And assuming that my parameter 'number' equals 2

I would expect a Value returned of 8, as the lookup function would round my input number 2 up to the nearest number in the range (3) and then return the associated value.

Can anyone tell me how I might achieve the same thing in C# code? Assuming the use of a Dictionary<int, int>()

Many thanks in advance

Ian

@HimBromBeere In this case the function would round UP to the nearest key — Ian, Dec 14 '15 at 14:20
You could use an ordered collection and a binary search algorithm. If you insist on a dictionary that would be `O(n)` since you have to look at all keys. — Tim Schmelter, Dec 14 '15 at 14:22
What happens if the `number` is 10 (basically a number that is higher than the highest key)? — juharr, Dec 14 '15 at 14:34

score 0 · Answer 1 · answered Dec 14 '15 at 14:23

0

You can leverage the Keys property of IDictionary<TKey, TValue>:

var dictionary = new Dictionary<int, int> { { 1, 2 }, { 3, 8 }, { 9, 1 } };
var key = dictionary.Keys.Where(a => a >= 2).OrderBy(a => a).First();
var value = dictionary[key];

answered Dec 14 '15 at 14:23

Albireo

10,977
13
62
96

score 0 · Answer 2 · edited May 23 '17 at 11:44

0

If you insist on a dictionary you could use following LINQ query:

Dictionary<int, int> dictionary = new Dictionary<int, int>() { 
    {1,2} ,{3,8} ,{9,1} 
};

int searchKey = 2;
int value;

if (dictionary.ContainsKey(searchKey))
    value = dictionary[searchKey];
else
{
    int nearestKey = dictionary.Keys
        .Select(i => new { Value = i, Diff = Math.Abs(i - searchKey) })
        .OrderBy(x => x.Diff)
        .ThenBy(x => x.Value > searchKey ? 0 : 1) // in case of ties you want the higher number
        .Select(x => x.Value)
        .First();
    value = dictionary[nearestKey];
}

this would be O(n) since you have to look at all keys. If you could use an ordered collection and a binary search algorithm it would be O(log n). So you could use a SortedDictionary<TKey, TValue> or SortedList<TKey, TValue>. Differences

With a SortedList you could use this extension method. Then it's simple:

int index = dictionary.FindFirstIndexGreaterThanOrEqualTo(2);
int value = dictionary[dictionary.Keys[index]];

edited May 23 '17 at 11:44

Community

1
1

answered Dec 14 '15 at 14:33

Tim Schmelter

450,073
74
686
939

Your method is O(N*log(N)) as you're sorting the entire set just to search for one value. – Servy Dec 14 '15 at 14:56
@Servy: what method do you refer to? My second approach presumes that OP uses a `SortedList` in the first place. I also didn't know that performance was a key criterion for OP. – Tim Schmelter Dec 14 '15 at 14:58
I'm referring to the original revision, where you suggest sorting the entire contents of the dictionary just to find one value. – Servy Dec 14 '15 at 15:02
@Servy: you have commented 5 minutes after i've edited my answer. Feel free to provide a more efficient approach. I'm sure there is one. – Tim Schmelter Dec 14 '15 at 15:07

score 0 · Answer 3 · answered Dec 14 '15 at 14:47

        var input = 2;
        var dictionary = new Dictionary<int, int> { { 1, 2 }, { 3, 8 }, { 9, 1 } };

        var smallestDifference = int.MaxValue;
        var keys = new List<int>();

        if (dictionary.ContainsKey(input))
        {
            return dictionary[input];
        }

        foreach (var entry in dictionary)
        {
            var difference = entry.Key - input;
            if (difference < smallestDifference)
            {
                smallestDifference = difference;
                keys = new List<int>() { entry.Key };
            }
            else if (difference == smallestDifference)
            {
                keys.Add(entry.Key);
            }
        }

        var candidates = dictionary.Where(x => x.Key == smallestDifference).ToList();
        if ( candidates.Count == 1)
        {
            return candidates.SingleOrDefault();
        }
        return candidates.SingleOrDefault(y => y > input);

How to get the nearest key to a specified number in a dictionary?

3 Answers3