查找值小于搜索值的最大字典<整数，字符串>键

Question

我有一个Dictionary<int,string>，它的升序如下：

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

我有var myValue = 3000.52

我需要找到比我的值小的最大myDictionary密钥。在这种情况下，我需要返回2500。

我试过：

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

但是，正如您所期望的，所有较小的值也都匹配。

如何找到小于搜索值的最大关键字？

Answer 1

我认为使用LinQ是最简单的方法：

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

Answer 2

您可以从字典键创建一个List<int>。如果你需要经常查找，我会保存这个列表。然后您可以使用List.BinarySearch查找最近的密钥：

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返回排序List<T>中项目的从零开始的索引（如果找到项目）；否则，负数，它是大于项的下一个元素的索引的按位补码，或者，如果没有更大的元素，则是Count的按位补码。

Answer 3

Giorgos的答案是使用Dictionary所能做的最好的答案，但它会很慢，因为这将搜索整个密钥空间。如果你想要一些快速的东西，C5集合库有很多.NET所缺乏的功能

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

它将在O（logn）中执行，随着字典大小的增长，效率会高得多。

Answer 4

您可以使用整数来跟踪最高值。

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