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

Question

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

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

Answer 1

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

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

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