有效地找到最近的字典键
我在SortedDictionary有一堆日期和货币值，对应于在合约定义的复利日期计算到未来的贷款余额。 有没有一种有效的方法来查找最接近给定值的日期键？ （具体而言，最接近的键小于或等于目标）。 关键是只在值改变时存储数据，但有效地回答“x日期余额是什么？”的问题。 对于范围内的任何日期。
一个类似的问题被问到（ 什么.NET字典支持“找到最近的密钥”操作？ ），当时答案是“不”，至少来自回复的人，但那是差不多3年前的事。
如何在排序字典中找到两个键之间的点的问题提出了天真迭代所有键的明显解决方案。 我想知道是否存在任何内置框架函数来利用密钥已经在内存中索引和排序的事实 – 或者是内置的Framework集合类，它可以更好地适应这种类型的查询。
由于SortedDictionary在键上排序，因此您可以使用键创建键的排序列表
var keys = new List(dictionary.Keys);
然后在其上有效地执行二进制搜索 ：
var index = keys.BinarySearch(key);
正如文档所述，如果index是正数或零，则密钥存在; 如果它是负数，那么~index是在它存在的情况下可以找到key的索引。 因此，“立即更小”的现有密钥的~index - 1是~index - 1 。 确保正确处理key小于任何现有键和~index - 1 == -1的边缘情况。
当然，如果keys构建一次然后重复查询，上述方法才有意义; 因为它涉及迭代整个键序列并进行二进制搜索，如果你只想搜索一次就没有意义。 在这种情况下，即使是天真的迭代也会更好。
更新
正如digEmAll正确指出的那样，您也可以切换到SortedList以便Keys集合实现IList （SortedDictionary.Keys不会）。 该接口提供了足够的function来手动执行二进制搜索，因此您可以使用此代码并使其成为IList的扩展方法。
您还应该记住，如果项目没有以已排序的顺序插入， SortedList在构造期间的性能比SortedDictionary更差，尽管在这种特殊情况下很可能按时间顺序（排序）顺序插入日期，这将是完美的。
所以，这并没有直接回答你的问题，因为你特意要求.NET框架内置的东西，但面对类似的问题，我发现以下解决方案效果最好，我想在这里发布其他的搜索。
我使用了C5 Collections （ GitHub / NuGet ）中的TreeDictionary ，这是一个红黑树的实现。
它具有Predecessor / TryPredecessor和WeakPredessor / TryWeakPredecessor方法（以及后续的类似方法），可以轻松找到最近的项目。
在我看来，更有用的是RangeFrom / RangeTo / RangeFromTo方法，它们允许您检索键之间的一系列键值对。
请注意，所有这些方法也可以应用于TreeDictionary集合，它们也允许您仅使用键。
它确实是一个非常简洁的实现，类似的东西应该在BCL中。
如果您需要使用插入交错查询（除非您的数据到达预先排序，或者集合总是很小），则无法使用SortedList ， SortedDictionary或任何其他“内置”.NET类型有效地查找最近的键。 。
正如我在你引用的另一个问题上提到的，我创建了三个与B +树相关的数据结构，为任何可排序的数据类型提供了find-nearest-keyfunction： BList ， BDictionary和BMultiMap 。 这些数据结构中的每一个都提供了FindLowerBound()和FindUpperBound()方法，它们的工作方式类似于C ++的lower_bound和upper_bound 。
public static DateTime RoundDown(DateTime dateTime) { long remainingTicks = dateTime.Ticks % PeriodLength.Ticks; return dateTime - new TimeSpan(remainingTicks); }