如何高效地搜索具有不等式的排序集？

好吧，说我有一个类型为int的强类型SortedSet。我想找到集合中小于x的最大数字。如何高效地搜索具有不等式的排序集？

也许这是错误的数据结构，但我直觉的想法是，我有一个排序的集合。毫无疑问，我应该能够通过.NET框架进行这种搜索。

2016-05-11 Shiv

由于SortedSet不提供通过索引直接访问你必须依靠枚举（线性搜索 - 为O（n））。一种可能更好的方法是使用SortedSet.GetViewBetween和Last，但它看起来不像你可以得到的最后一个元素，但无论如何都没有枚举所有元素。

收集与指数直接访问（即List）将让你做O（LG n）的二进制搜索性能 - 因此使用List.BinarySearch时，如果你需要大量的复制搜索到列表可以与ToList提供更好的整体性能（这给你你正在寻找的下一个元素的位置）。

// starting sample for BinarySearch approach 
// not handling case where item not in the list (x = 1). 
// List have to be sorted which is the case starting from sorted set: sortedSet.ToList() 
var list = new List<int>{ 1,3, 5, 7, 8,9}; 
var index = list.BinarySearch(8); 
Console.WriteLine(index < 0 ? list[~index - 1] : list[index-1]);

来源

2016-05-11 05:26:01

值得一提的是，必须在执行BinarySearch之前对列表进行排序 - 从msdn页面的备注部分：“列表必须已根据比较器实现进行排序;否则结果不正确。” –

@zohar OP从SortedSet开始，所以ToList将会产生排序列表。事实上，如果从其他一些数据开始，那么排序是第一步 - 但这比原始的线性搜索更糟糕。 –

我完全同意你的看法，这就是为什么我提高了你的答案，但这也是我认为值得一提的原因 - 你的例子没有在有序集合上使用'.ToList（）'... –

除非我失去了一些东西，使用Linq的LastOrDefault扩展方法：

var lastBefore = set.LastOrDefault(num => num < x); // x is your search number 
if (lastBefore < set.ElementAt(0)) 
{ 
    // Nothing in the set is smaller 
} 
else 
{ 
    // lastBefore is the last number smaller then search number 
}

来源

2016-05-11 05:24:26

请注意，即使集合被排序并且通常会期望O（lg n）性能，但这是O（n），但就我所知，这是使用'SortedSet'的最佳结果。 –

如何高效地搜索具有不等式的排序集？

回答

相关问题