CODEWITHSUNDEEP
c#dictionary
Satchmode
Satchmode

Reputation: 133

Finding closest lower key of a number in a dictionary

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.

Upvotes: 2

Views: 2734

Answers (3)

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186668

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

Upvotes: 4

Arturo Menchaca
Arturo Menchaca

Reputation: 15982

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];

Upvotes: 1

James Dev
James Dev

Reputation: 3009

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; }
}

Upvotes: -3

Related Questions