c# - SortedList<K ,V> 上是否有 Lower Bound 函数？

Question

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

伙计们 - 请再读一遍这个问题。 我不需要返回 key (如果存在)的函数。我对没有精确 key 匹配的情况很感兴趣。

我对 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);
}