上有下界函数SortedList<K ,V>吗?该函数应返回等于或大于指定键的第一个元素。还有其他支持此的类吗?
SortedList<K ,V>
伙计们-请再读一次问题。 我不需要返回键(如果存在)的函数。 我对没有精确的密钥匹配的情况感兴趣。
我对O(log n)time感兴趣 。这意味着我对foreach循环没有问题,但是希望有一种有效的方法来做到这一点。
我对此做了一些测试。
Linq语句没有被编译器或运行时机器优化,因此它们遍历所有集合元素并且速度很慢O(n)。根据Mehrdad Afshari的答案,以下是在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; }
二进制搜索SortedList.Keys集合。
SortedList.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); }