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

Question

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

也许这不是正确的数据结构，但我的直觉认为我有一个已排序的集合。 我应该能够通过.NET框架来进行此类搜索，这是有意义的，对吗？

- Shiv

Answer 1

由于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]);

- Alexei Levenkov

---

值得一提的是，在执行二分查找之前，列表必须被排序。来自 MSDN 页面的备注部分：“List<T> 必须根据比较器实现进行排序；否则，结果将不正确。” - Zohar Peled

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - Alexei Levenkov

我完全同意你的观点，这就是为什么我给你的答案点了赞，但我认为值得一提的是 - 你的示例没有在有序集合上使用.ToList()... - Zohar Peled

Answer 2

除非我漏掉了什么，可以使用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
}

- Zohar Peled

---

请注意，即使集合已经排序，这段代码的时间复杂度仍为O(n)，而通常情况下我们期望的是O(lg n)的性能，但据我所知，使用SortedSet时这已经是最好的结果了。 - Alexei Levenkov

很遗憾，SortedSet没有O(log n)的搜索方法可供利用，这让人感到失望！ - Shiv