是否有下界函数在排序列表？

StackOverflow https://stackoverflow.com/questions/594518

  •  09-09-2019
  •  | 
  •  

题

有一个SortedList<K ,V>下限功能？该函数返回比指定的键等于或大于第一要素。是否有支持该其它的类？

家伙 - 请再次阅读问题。 我并不需要它是否存在，返回键的功能。我感兴趣的场景时，有没有确切的关键匹配。

<强>我感兴趣的O（log n）的时间即可。这意味着我没有与foreach循环出了问题，而是想有这样的一个有效的方法。

我已经做了这方面的一些试验。

LINQ的语句没有既不编译器也不运行时优化的机器，所以它们穿行所有收集元件和慢为O（n）。基于迈赫达德Afshari的答案，这里是一个二进制搜索，在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集合。

在这里，我们走了。这是为O（log 名词的）：

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

其他提示

我会使用LINQ去（假设你在使用C＃3），但使用FirstOrDefault的，需要一个谓词过载：

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

（很多的其它可枚举方法也可以采取谓词这是一个很好的快捷方式）

不知道一个，但它是一个简单的LINQ语句：

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

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

修改

DaveW的版本：

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

做同样的工作，但可能会更快，你必须虽然测试它。

也可以编写自己的扩展方法来做到这一点。请注意，所有这些功能都不能保证在sequesce去。

这应该可以更快，这取决于排序列表的实现。

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;
}
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top