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

Question

好的，假设我有一个 int 类型的强类型 SortedSet。我想找到集合中小于 x 的最大数字。

也许这是错误的数据结构，但我的直觉是我有一个排序的集合。我应该能够通过 .NET 框架进行这种类型的搜索当然有意义吗？

Answer 1

除非我遗漏了什么，否则请使用 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
}

Answer 2

由于 SortedSet 不提供通过索引的直接访问，您必须依赖枚举（线性搜索 - O(n)）。一种可能更好的方法是使用 SortedSet.GetViewBetween 和 Last，但看起来您无法在不枚举视图中所有元素的情况下获取最后一个元素。

通过索引直接访问的集合（即 List）可以让您以 O(lg n) 性能进行二进制搜索 - 因此如果您需要搜索很多内容，则可以使用 ToList 在使用 List.BinarySearch 时提供更好的整体性能（它为您提供下一个元素到您正在寻找的元素的位置）。

// 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]);

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

How to efficiently search a sortedset with an inequality?

c#

.net-4.0

sortedset