Finding closest lower key of a number in a dictionary

Question

I have a Dictionary;

Dictionary<int, float> delta = new Dictionary<int, float>();

which contains:

0,  45,2345
7,  25,3556
18, 23,2334

How can i find the value of the closest, lower key to a number?

Imagine I have the number 16, id like to find the value of key 7. Same for 4, id like the value of key 0.

Preferably i'd also like the fastest way to do this, since i have to run the operation several million times.

I use C#, .NET 4.

A `Dictionary` is useless for what you are trying to do. A `SortedList<>` would be better, but sadly it doesn't have a method to search for the nearest element. An array/`List<>` manually ordered, and searched with `BinarySearch` is probably the best solution. — xanatos, Feb 25 '16 at 15:37
@juharr Better a `SortedList<>`. The `Keys` property is a `IList<>`, so you can `BinarySearch` it — xanatos, Feb 25 '16 at 15:40
@xanatos `BinarySearch` is defined for `List` not `IList` also it would only return on an exact match so the OP would still need to implement a nearest binary search. — juharr, Feb 25 '16 at 15:43
@juharr You'll need to implement it... Still better than with `SortedDictionary<>` where you don't even have the "building blocks" to implement it. — xanatos, Feb 25 '16 at 15:44
@xanatos What "building blocks"? I'm not saying one is better than the other I'm just not seeing exactly why you think `SortedList` is better. — juharr, Feb 25 '16 at 15:45
@juharr `You could use SortedDictionary and then implement a binary search on the Keys property collection` You can't. The `Keys` property collection is a `ICollection`, not a `IList`... So no direct access to index `ix`, necessary for a binary search. At least `SortedList.Keys` is a `IList`, so you can implement the binary search. — xanatos, Feb 25 '16 at 15:47
I don't see why the downvotes on this one... I think this is a great question. — Brandon, Feb 25 '16 at 15:52
Mmmh... Someone had alread asked something like it: http://stackoverflow.com/questions/594518/is-there-a-lower-bound-function-on-a-sortedlistk-v For a SortedList<> it returns the first >= of the searched key, but clearly it is easy from there to go index-1 and return the last <= — xanatos, Feb 25 '16 at 15:53
@Brandon I'd guess they are for a lack of research effort as the OP didn't actually try anything or at least didn't show what they might have tried. — juharr, Feb 25 '16 at 15:54
@juharr Okay, I'll give you that there was no "I tried this...". I think I've spent too long in the SO review queue :\ — Brandon, Feb 25 '16 at 15:58

Dmitry Bychenko · Answer 1 · 2016-02-25T16:05:20.653

3

I suggest using sorted list instead of dictionary, e.g.

  List<Tuple<int, float>> delta = new List<Tuple<int, float>>() {
    new Tuple<int, float>(0, 45.2345F),
    new Tuple<int, float>(7, 25.3556F),
    new Tuple<int, float>(18, 23.2334F),
  };

  // Sort the list 
  delta.Sort((left, right) => left.Item1.CompareTo(right.Item1));

  // ... And binary search then
  int index = delta.BinarySearch(new Tuple<int, float>(16, 0.0F),
    Comparer<Tuple<int, float>>.Create(
      (left, right) => left.Item1.CompareTo(right.Item1)));

  if (index < 0) // If there's not exact match
    index = ~index - 1; // - 1 - ...then return low bound
  else           // in case of exact match
    index -= 1;  // -= 1 ... return low bound as well

  ...
  // Test: "(7, 25.3556)"
  Console.Write(delta[index].ToString());

Please note, that you can well have index == -1 in case that there're no items lower than the target

edited Feb 25 '16 at 16:05

answered Feb 25 '16 at 15:50

Dmitry Bychenko

180,369
20
160
215

I think you will need to handle the "exact match" edge case differently, since the OP wants the closest lower number - I think this code will return the exact match itself if it matches exactly. Also the edge case where there is no number lower than the target. – Matthew Watson Feb 25 '16 at 16:00
Thank you for the elaborate solution to my problem. I see there are multiple solutions and although yours works just as well, The answer i've marked is a cleaner piece of code so im gonna run with that one. – Satchmode Feb 25 '16 at 16:57

score 1 · Accepted Answer · answered Feb 25 '16 at 15:59

You can filters the keys keeping only the lowers, then gets the max key:

Dictionary<int, float> delta = new Dictionary<int, float>();
var key = 16;

var maxKey = delta.Keys.Where(k => k < key).Max();
var value = delta[maxKey];

However, as noted in the comments a better approach is use classes like SortedDictionary<> or SortedList<>.

If all add/remove operations runs first, and later only searches are performed a solution can be convert the keys to array (O(N)) and use Array.BinarySearch() method (O(log N)):

SortedDictionary<int, float> sortedDict = new SortedDictionary<int, float>();

// Add-Remove operations

var keys = sortedDict.Keys.ToArray();

// Search operations

int maxKey = Array.BinarySearch(keys, key);
float value = maxIndex >= 0 ? sortedDict[maxKey] : sortedDict[~maxIndex - 1];

Thanks for the quick and insightful solution to the problem. The code looks clean and easy to use. Thanks! — Satchmode, Feb 25 '16 at 16:58

James Dev · Answer 3 · 2016-02-25T15:48:16.117

-3

This should give you what you want

List<Store> list = new List<Store> { new Store() { Number = 0, Number2 = 452345F }, new Store() { Number = 7, Number2 = 253556F }
        , new Store() { Number = 18, Number2 = 232334F }};
int number = 16;

var closest = list.Aggregate((x, y) => Math.Abs(x.Number - number) < Math.Abs(y.Number - number) ? x : y);

Console.WriteLine(closest.Number2);

class Store
{
    public int Number { get; set; }
    public float Number2 { get; set; }
}

edited Feb 25 '16 at 15:48

answered Feb 25 '16 at 15:41

James Dev

2,979
1
11
16

This answer is a straight copy of: http://stackoverflow.com/questions/5953552/how-to-get-the-closest-number-from-a-listint-with-linq And it is not right, for this question. Above will return x or y, being closest higher or closest lower... What is needed here is only Math.Abs(x - number) – Richard Tyregrim Feb 25 '16 at 15:43
@RichardEriksson Updated answer – James Dev Feb 25 '16 at 15:48

Finding closest lower key of a number in a dictionary

3 Answers3