Как эффективно искать сортировку с неравенством?

Question

Хорошо, скажем, у меня есть строго типизированный SortedSet типа int. Я хочу найти наибольшее число в наборе, которое меньше х.

Возможно, это неправильная структура данных, но мое интуитивное мышление заключается в том, что у меня есть отсортированная коллекция. Конечно, имеет смысл, что я должен быть в состоянии сделать этот тип поиска через.NET Framework?

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

Answer 2

Если я что-то упустил, используйте Линк 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
}