如何在排序字典中找到两个键之间的点
我有一个排序字典，包含测量数据点作为键/值对。 为了确定非测量数据点的值，我想使用相应值的线性插值来推断两个已知键之间的值。 一旦我有两个键/值对，我就明白了如何计算非测量数据点。 我不知道的是如何找出它之间的关键。 有没有比“for”循环（我正在考虑函数/ LINQ查询）更优雅的方法来确定我的数据点位于哪两个键之间？
这样的东西会起作用：
dic.Keys.Zip(dic.Keys.Skip(1), (a, b) => new { a, b }) .Where(x => xa <= datapoint && xb >= datapoint) .FirstOrDefault(); 这会使用它们被排序的事实遍历它们，并按顺序将所有两个键相互比较 – 因为一旦找到第一个匹配，LINQ就会变得很懒，遍历将停止。
标准C＃答案都是O（N）复杂度。 有时你只需要一个相当大的有序集合中的一个小子集。 （所以你没有迭代所有的键）标准的C＃集合对你没有帮助。 解决方案如下： http ： //www.itu.dk/research/c5/使用C5集合库中的IntervalHeap。 此类支持GetRange（）方法，并将以O（log N）复杂度查找startkey，并以O（N）复杂度迭代该范围。 如果性能至关重要，这对大数据集肯定有用。 例如，游戏中的空间分区
您可能会问以下问题：
myDictionary.Keys.Where(w => w > start && w < end)
常规循环应该可以在这里：
IEnumerable keys = ...; //ordered sequence of keys double interpolatedKey = ...; // I'm considering here that keys collection doesn't contain interpolatedKey double? lowerFoundKey = null; double? upperFoundKey = null; foreach (double key in keys) { if (key > interpolatedKey) { upperFoundKey = key; break; } else lowerFoundKey = key; }
您可以在C＃中使用LINQ，但代码更短但效率更低：
double lowerFoundKey = key.LastOrDefault(k => k < interpolatedKey); double upperFoundKey = key.FirstOrDefault(k => k > interpolatedKey);
为了有效地使用LINQ，它应该有一个方法， 在F＃中使用参数2进行窗口化。它将在keys集合中返回相邻对的IEnumerable 。 虽然在LINQ常规foreach循环中缺少此函数应该没问题。
我不认为SortedDictionary上有一个函数可以让你找到比迭代元素更快的元素周围的元素。 （+1到BrokenGlass解决方案）
为了能够更快地找到项目，您需要切换到其他结构。 即SortedList提供类似的function，但允许索引其Key集合，因此您可以使用二进制serach来查找范围。