LINQ Query Determine Input is in List Boundaries?

Question

I have a List of longs from a DB query. The total number in the List is always an even number, but the quantity of items can be in the hundreds.

List item [0] is the lower boundary of a "good range", item [1] is the upper boundary of that range. A numeric range between item [1] and item [2] is considered "a bad range".

Sample:

var seekset = new SortedList();
var skd= 500;
while( skd< 1000000 )
{
seekset.Add(skd, 0);
skd = skd+ 100;
}

If an input number is compared to the List items, if the input number is between 500-600 or 700-800 it is considered "good", but if it is between 600-700 it is considered "bad".

Using the above sample, can anyone comment on the right/fast way to determine if the number 655 is a "bad" number, ie not within any good range boundary (C#, .NET 4.5)?

If a SortedList is not the proper container for this (eg it needs to be an array), I have no problem changing, the object is static (lower case "s") once it is populated but can be destroyed/repopulated by other threads at any time.

@Habib It's in .NET: http://msdn.microsoft.com/en-us/library/system.collections.sortedlist.aspx — Dan Esparza, Oct 18 '13 at 17:47
@DanEsparza, that non generic version, The one used in question is Generic, or is there something I am missing — Habib, Oct 18 '13 at 17:49
@Habib Excellent point. The closest I can find has 2 type params in the generic constructor: http://msdn.microsoft.com/en-us/library/ms132319.aspx — Dan Esparza, Oct 18 '13 at 17:52
Also: Jon Skeet's commentary on the differences between a SortedList and a SortedDictionary may be apropos to the discussion on performance: http://stackoverflow.com/a/935631/19020 — Dan Esparza, Oct 18 '13 at 17:54

score 1 · Answer 1 · answered Oct 18 '13 at 17:06

If you only have a few hundred items then it's really not that bad. You can just use a regular List and do a linear search to find the item. If the index of the first larger item is even then it's no good, if it's odd then it's good:

var index = data.Select((n, i) => new { n, i })
    .SkipWhile(item => someValue < item.n)
    .First().i;

bool isValid = index % 2 == 1;

If you have enough items that a linear search isn't desirable then you can use a BinarySearch to find the next largest item.

var searchValue = data.BinarySearch(someValue);
if (searchValue < 0)
    searchValue = ~searchValue;

bool isValid = searchValue % 2 == 1;

score 1 · Answer 2 · answered Oct 18 '13 at 17:23

I am thinking that LINQ may not be best suited for this problem because IEnumerable forgets about item[0] when it is ready to process item[1].

Yes, this is freshman CS, but the fastest in this case may be just

// untested code
Boolean found = false;
for(int i=0; i<seekset.Count; i+=2)
{
   if (valueOfInterest >= seekset[i] &&
       valueOfInterest <= seekset[i+1])
   {
       found = true;
       break;   // or return;
   }
}

I apologize for not directly answering your question about "Best approach in Linq", but I sense that you are really asking about best approach for performance.

score 1 · Accepted Answer · answered Oct 18 '13 at 17:27

1

The following works, assuming the list is already sorted and both of each pair of limits are treated as "good" values:

public static bool IsGood<T>(List<T> list, T value)
{
    int index = list.BinarySearch(value);   
    return index >= 0 || index % 2 == 0;
}

answered Oct 18 '13 at 17:27

Matthew Strawbridge

19,940
10
72
93

+1: I appreciate the cleverness of this solution. It is also likely faster than my answer at any scale. – philologon Oct 18 '13 at 17:31
@KingKing : Good catch. But this is easy to overcome by making the two checks serial if's. – philologon Oct 18 '13 at 18:03
@KingKing It's correct: if the index is positive then it's an exact match of one of the boundaries, so it's in bounds (according to the assumptions I listed). – Matthew Strawbridge Oct 18 '13 at 18:58
@MatthewStrawbridge I didn't doubt your idea, I just thought the `%` operator is not able to perform on a `negative` integer but looks like it is. – King King Oct 18 '13 at 19:12

LINQ Query Determine Input is in List Boundaries?

3 Answers3