SortedList <K,V>上是否有下限功能？

Question

是否有下限功能SortedList<K ,V>？该函数应返回等于或大于指定键的第一个元素.还有其他类支持这个吗？

伙计们 - 请再次阅读这个问题.如果它存在,我不需要返回键的函数.当没有确切的密钥匹配时,我对场景感兴趣.

我对O(log n)时间感兴趣.这意味着我没有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;
}

Answer 1

二进制搜索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);
}

Answer 2

我会使用 LINQ（假设您使用的是 C#3），但是使用 FirstOrDefault 的重载，它需要一个谓词：

first = sortedList.FirstOrDefault(x => x >= theObjectForComparison);

（许多其他 Enumerable 方法也可以使用谓词，这是一个很好的捷径）