SortedList <K，V>上有下限函数吗？
SortedList<K ,V>上有下限函数吗？ 该函数应返回等于或大于指定键的第一个元素。 还有其他一些课程支持吗？
伙计们 – 请再次阅读这个问题。 如果它存在，我不需要一个返回键的函数。 如果没有确切的密钥匹配，我对情况感兴趣。
我对O（log n）时间感兴趣 。 这意味着我没有foreach循环的问题，而是希望有一个有效的方法来做到这一点。
我已经做了一些testing。
Linq语句没有被编译器和运行时机器优化，所以他们遍历所有的集合元素，并且速度很慢（O（n））。 基于Mehrdad Afshari的回答，这里是一个二进制search在Keys集合的O（log n）中工作：
public static int FindFirstIndexGreaterThanOrEqualTo<T>( this IList<T> sortedCollection, T key ) where T : IComparable<T> { int begin = 0; int end = sortedCollection.Count; while (end > begin) { int index = (begin + end) / 2; T el = sortedCollection[index]; if (el.CompareTo(key) >= 0) end = index; else begin = index + 1; } return end; }
二进制searchSortedList.Keys集合。
开始了。 这是O（log n ）：
private static int BinarySearch<T>(IList<T> list, T value) { if (list == null) throw new ArgumentNullException("list"); var comp = Comparer<T>.Default; int lo = 0, hi = list.Count - 1; while (lo < hi) { int m = (hi + lo) / 2; // this might overflow; be careful. if (comp.Compare(list[m], value) < 0) lo = m + 1; else hi = m - 1; } if (comp.Compare(list[lo], value) < 0) lo++; return lo; } public static int FindFirstIndexGreaterThanOrEqualTo<T,U> (this SortedList<T,U> sortedList, T key) { return BinarySearch(sortedList.Keys, key); }
我会用LINQ（假设你正在使用C＃3），但是使用带谓词的FirstOrDefault的重载：
first = sortedList.FirstOrDefault(x => x >= theObjectForComparison);
（许多其他Enumerable方法也可以带谓词，这是一个不错的捷径）
没有意识到，但这是一个简单的LINQ声明：
first = sortedList.Where(x => x >= theObjectForComparison).FirstOrDefault();
first要么是传递比较的第一个对象，要么是default(T) （通常为null ）。
编辑
DaveW的版本：
first = sortedList.FirstOrDefault(x => x >= theObjectForComparison);
做同样的工作，但可能会更快，你不得不testing它。
或者你可以写自己的扩展方法来做到这一点。 请注意，所有这些function都不能保证一定会有效。
希望这应该是更快，取决于SortedList的实现。
public static int FindFirstIndexGreaterThanOrEqualTo<K, V>( this SortedList<K, V> sortedCollection, K key ) where V : new() { if (sortedCollection.ContainsKey(key)) { return sortedCollection.IndexOfKey(key); } sortedCollection[key] = new V(); int retval = sortedCollection.IndexOfKey(key); sortedCollection.Remove(key); return retval; }
