不等号でソートセットを効率的に検索するにはどうすればよいですか？

Question

私はint型の厳密に型指定されたSortedSetを持っています。 xより小さい集合の中で最大の数を見つけたい。

これは間違ったデータ構造ですが、直感的な考えはソートされたコレクションがあることです。確かに、私はこのタイプの検索を.NETフレームワーク経由で行うことができるはずです。

Answer 1

をあなたが列挙（線形検索 - O（N））に依存する必要がインデックスによって直接アクセスすることはできません。おそらくより良い方法はSortedSet.GetViewBetweenとLastですが、最後の要素を取得できるようには見えません。 （あなたがリストに多くのコピーを検索する必要がある場合List.BinarySearchを使用した場合ToListとのより良い全体的なパフォーマンスを与えることができる -

インデックス（すなわちList）によって直接アクセスしてコレクションを使用すると、O（LG n）で性能を持つバイナリ検索をやらせるだろうあなたが探しているものの次の要素の位置を与える）。

// 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拡張メソッドを使用します。SortedSetので

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 
}