SortedList<K, V>是否有下限函数？

Question

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

各位 - 请再次阅读问题。我不需要一个返回已存在键的函数。我关心的是没有精确匹配的情况。

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

- agsamek

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

- Mehrdad Afshari

---

agsamek：不，它没有重新生成。它将返回一个内部类KeyList的实例，该实例提供对原始集合中元素的直接访问。在此过程中不会复制任何内容。 - Mehrdad Afshari

为避免溢出：变量m = low + (hi - low)/2。 - Erwin Mayer

当列表为空时，该方法会抛出异常... 它应该返回0，不是吗？ - digEmAll

这个仓库包含了 C# 数组、列表和排序列表类的 lower_bound() 和 upper_bound() 实现： https://github.com/mohanadHamed/MNDSearchUtil - Mohanad S. Hamed

@AgentFire 对于所有有效的基数，O(log(n, base1)) == O(log(n, base2))。证明：log(n, base1) = log(n, base2) * log(base1, base2)，而log(base1, base2)是一个常数，使其渐近无关紧要。因此，在讨论某个东西的O(log(..))时，可以省略基数。 - Mehrdad Afshari

Answer 2

如果您使用的是C#3，我建议您使用LINQ，并使用带有谓词的FirstOrDefault重载：

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

很多其他的Enumerable方法也可以接受谓词，这是一种很好的快捷方式。

- Dave W

Answer 3

我不知道是否有现成的，但这是一个简单的LINQ语句：

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

first将是第一个通过比较的对象或者default(T)（通常为null）。

编辑

DaveW的版本：

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

这个做的是同样的工作，但有可能会更快，不过你需要进行测试。

- Garry Shutler

Answer 4

public static TValue? LowerBound<TKey, TValue>(this SortedList<TKey, TValue> list, TKey key) where TKey : notnull, IComparable<TKey>
{
    var comparer = list.Comparer;

    #region Short-Circuits

    if (list.Count == 0) //empty list
        return default;
    if (list.ContainsKey(key)) 
       return list[key]; //"The function should return the first element equal"

    if (comparer.Compare(list.Keys[list.Keys.Count - 1], key) < 0)
        return default; // if all elements are smaller, return default

    if (comparer.Compare(list.Keys[0], key) > 0)
        return list[list.Keys[0]]; //if the first element is greater, return it

    #endregion Short-Circuits

    int range = list.Count - 1; //the range between of first and last element to check
    int itemIndex = 1;          //the default value of index is 1 since 0 was already checked above
    while (range > 0)
    {
        int halfRange = range / 2;               //cut the search range in half
        int indexTmp = itemIndex + halfRange;    //set the current item to compare
        if (comparer.Compare(list.Keys[indexTmp], key) < 0)
        {
            //the current item is less than the given key
            itemIndex = indexTmp + 1;   //set the current item to the item after the compared item
            range = (range - halfRange - 1); //move the remaining range to the right
        }
        else
        {
            //the current item is greater than the given key (we have already checked equal above in short-circuits)
            range = halfRange; //move the remaining range to the left
        }
    }
    return list[list.Keys[itemIndex]];
}

- Ferdinand Stapenhorst

---

好的，这个方便直接获取值（正如OP所要求的）。相反，我们不区分列表为空/搜索的键大于所有键的情况，并且我们碰巧在下限处找到一个等于默认值的值。但是，如果默认值无效，或者我们知道应该有一个下限，或者我们真的希望默认值不存在下限，则可以使用此选项。此外，如果我们确实想保留此信息，我们可以使函数返回成功的bool + TValue。如果您需要索引，请参见mmx的答案。 - hsandt

Answer 5

或者您可以编写自己的扩展方法来实现此功能。请注意，所有这些函数都不能保证按照顺序执行。

- Migol

Answer 6

希望这样会更快，取决于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;
}

- Shannon Monasco