V>的SortedList<K上有下界函数吗？
V>的SortedList<K上有下界函数吗？
提问于 2009-02-27 12:15:13
SortedList<K ,V>上有下界函数吗？该函数应返回等于或大于指定键的第一个元素。有没有其他类支持这一点？
各位-请再读一遍问题。如果关键字存在，则不需要返回关键字的函数。我对没有精确的键匹配的场景感兴趣。
我对O( n) time感兴趣。这意味着我对foreach循环没有问题，但我更希望有一种有效的方法来做这件事。
我已经对此做了一些测试。
Linq语句既没有被编译器优化，也没有被运行时机器优化，所以它们遍历所有集合元素，并且速度很慢O(n)。基于Mehrdad的回答，这里是一个二进制搜索，它在Keys集合上以O(log )的方式工作：
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;
}回答 6
Stack Overflow用户
回答已采纳
发布于 2009-02-27 12:20:01
对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);
}Stack Overflow用户
发布于 2009-02-27 12:36:23
我会使用LINQ (假设你使用的是C#3)，但是使用带有谓词的FirstOrDefault重载：
first = sortedList.FirstOrDefault(x => x >= theObjectForComparison);(许多其他可枚举方法也可以接受谓词，这是一个很好的捷径)
Stack Overflow用户
发布于 2009-02-27 12:20:06
不知道有一个，但它是一个简单的LINQ语句：
first = sortedList.Where(x => x >= theObjectForComparison).FirstOrDefault();first或者是第一个通过比较的对象，或者是default(T) (通常是null)。
编辑
DaveW的版本：
first = sortedList.FirstOrDefault(x => x >= theObjectForComparison);做同样的工作，但可能会更快，但你必须测试它。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/594518
复制相关文章
相似问题