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

Question

好吧，說我有一個類型爲int的強類型SortedSet。我想找到集合中小於x的最大數字。

也許這是錯誤的數據結構，但我直覺的想法是，我有一個排序的集合。毫無疑問，我應該能夠通過.NET框架進行這種搜索。

Answer 1

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

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 
}