CODEWITHSUNDEEP
c#.net-4.0sortedset
Shiv
Shiv

Reputation: 1404

How to efficiently search a sortedset with an inequality?

Ok say I have a strongly typed SortedSet of type int. I want to find the largest number in the set that is less than x.

Maybe this is the wrong data structure for this but my intuitive thinking is that I have a sorted collection. Surely it makes sense that I should be able to do this type of search via the .NET framework?

Upvotes: 6

Views: 3291

Answers (3)

piju3
piju3

Reputation: 125

You can use the Min and Max properties to get the lowest and highest value of a set (which is internally a red-black tree) in O(log n) time. You can use GetViewBetween() to efficiently get a subset of the tree, and then you can use Min and Max on that search.

Creating the view performs a O(log n) search to find the first node in the range, and then any further searches will start from there (assuming the data hasn't changed), so the two operations are effectively a single binary search split in two.

Therefore to get the highest number less than x, you can simply use set.GetViewBetween(int.MinValue, x-1).Max. Using int.MinValue saves an unnecessary search to find the lowest value. Otherwise you could also use set.Min.

Also note that the limits are inclusive and there is no way to enumerate backwards, so if you want the number less than N you have to search for N-1, which is not a problem for integers, but could be a problem if you're using a custom key type or comparator.

Upvotes: 0

Alexei Levenkov
Alexei Levenkov

Reputation: 100527

Since SortedSet does not provide direct access by index you have to rely on enumeration (linear search - O(n)). One possibly better method is to use SortedSet.GetViewBetween and Last, but it does not look like you can get last element without enumerating all elements in view anyway.

Collection with direct access by index (i.e. List) would let you do binary search with O(lg n) performance - so if you need to search a lot copying to list could with ToList give better overall performance when using List.BinarySearch (which give you position of next element to one you are looking for).

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

Upvotes: 3

Zohar Peled
Zohar Peled

Reputation: 82474

Unless I'm missing something, use Linq's LastOrDefault extension method:

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
}

Upvotes: 1

Related Questions