1

I have a situation where I have a SortedList, but with very sparse entries. I would like to be able to find values for a range of keys, however I believe my solution is too 'brute force' like and is very slow.

SortedList<ushort, string> myList = new SortedList<ushort, string>();

myList.Add(3, "three");
myList.Add(2, "two");
myList.Add(4, "four");
myList.Add(11, "eleven");
myList.Add(23, "twenty three");
myList.Add(16, "sixteen");

// Get values where Key is > 12 and < 19
for (ushort i = 13; i < 19; i++)
{
    if(!myList.ContainsKey(i))
         continue;

    // Got a key!
}

In the case of my example, brute force might be okay, but if the keys are much larger, with thousands of empty keys between, this becomes a problem, is there a better way to do this?

Thanks.

Pineapple
  • 33
  • 4
  • 1
    Do you know what a binary search is? If not its probably a good place to start: https://en.wikipedia.org/wiki/Binary_search_algorithm . – Chris Jan 11 '18 at 10:45
  • 2
    You could do a binary search for the lower and upper bound. – CodeCaster Jan 11 '18 at 10:45
  • 1
    Does this answer help? https://stackoverflow.com/a/23807479/284240 – Tim Schmelter Jan 11 '18 at 10:46
  • Intersection of your range (Enumerable.Range(13, 19)) and myList.Keys? – yesenin Jan 11 '18 at 10:49
  • If you just want to get items between range , use `myList.Where(x => x.Key > 13 && x.Key < 19);` – Ehsan Ullah Nazir Jan 11 '18 at 10:54
  • @Chris Thanks, yes I know what a Binary Search is, but that only partially helps, because even though it will give the upper and lower bounds of existing keys, it does not solve the issue of getting keys in between those bounds... or maybe I am missing something. – Pineapple Jan 11 '18 at 10:56
  • Once you know the indices of the lower and upper bound (or their lower resp. higher values when missing), you can simply get all items by index in between. – CodeCaster Jan 11 '18 at 10:58
  • @EhsanUllahNazir Thanks! That works great, do you happen to know the performance of this though? – Pineapple Jan 11 '18 at 10:59
  • @CodeCaster But the keys in between will also be very sparse? Or do you not mean a linear search between the bounds? – Pineapple Jan 11 '18 at 11:01
  • @RamonBrand: Remember that `myList.Keys` will give you a collection containing just the keys - you then don't need to worry about it being sparse. – Chris Jan 11 '18 at 11:02
  • @Chris Absolutely, makes perfect sense now, thanks! How do I up vote a comment here? I see no way to vote, or can I as the op not vote on comments? Thanks again. – Pineapple Jan 11 '18 at 11:06
  • Its probably that you haven't got enough rep to vote on comments - I forget what you can and can't do as a 1 rep user. – Chris Jan 11 '18 at 11:40

0 Answers0