如何找到集合中的下一个最大密钥？

Question

假设我有一个用C＃编写的字典。假设键具有可比性，我如何找到大于给定k（与字典键的类型相同）的最小键？但是，我想通过SortedDictionary这样的集合有效地做到这一点。

显然，如果不是高效地执行操作的问题，则可以从任何字典开始，提取其键，然后使用带有合适谓词的First方法。但这将在线性时间（按键的数量）中执行，如果一个键具有一组排序的键，则一个人应该能够在记录时间内找到该键。

谢谢。

Answer 1

的SortedList<TKey, TValue>类实现IDictionary<TKey, TValue>并具有IndexOfKey方法; 我认为这就是您想要的：

// I'm just going to pretend your keys are ints
var collection = new SortedList<int, string>();

// populate collection with whatever

int k = GetK(); // or whatever

int kIndex = collection.IndexOfKey(k);

int? smallestKeyGreaterThanK = null;
if (collection.Count > kIndex + 1)
    smallestKeyGreaterThanK = collection.Keys[kIndex + 1];

根据MSDN文档：

该方法执行二进制搜索；因此，此方法是O（log n）操作。

编辑：如果不能确定字典中是否包含要查找的键（您只想要第二大的键），则仍然有一种方法可以利用.NET中现有的二进制搜索方法来实现目的。您说您正在寻找一种“高效”的解决方案；该标准如果你的术语的含义如下配合你的时间（和代码行而言）。另一方面，如果您是用内存使用或性能来表示的话，那可能不是理想的选择。无论如何：

List<int> keysList = new List<int>(collection.Keys);
int kIndex = keysList.BinarySearch(k);

现在，BinarySearch将为您提供所需的内容，但是如果钥匙不在那儿，那就有点古怪了。MSDN文档中的返回值如下：

的从零开始的索引项的排序List<T>，如果项目被发现; 否则，负号即是大于下一个元素的索引的按位求补项，或者，如果没有更大的元件，计数的按位求补。

这意味着您需要添加另一行：

kIndex = kIndex >= 0 ? kIndex : ~kIndex;