在SortedList上是否存在下界函数？

小编典典

在SortedList上是否存在下界函数？

上有下界函数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;
}

阅读 305

2020-05-19

共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);
}

2020-05-19