1

Folks,

Given a set of sorted values (perhaps in a List<T>, SortedList<T,K>, etc.) what's the best way to go about evaluating inequalities (greater-than, less-than, greater-than-or-equal-to, less-than-or-equal-to a given value)? Possible with any of the standard .net types? Or easily coded up? Any pointers are greatly appreciated.

EDIT - of course I'm trying to make this as fast as possible. needs to be highly performant

Suraj
  • 35,905
  • 47
  • 139
  • 250
  • 1
    This question doesn't make sense. – jason Nov 12 '10 at 17:46
  • how so? I think its pretty simple. I have a sorted list of doubles. I want to find all values in the list that are greater than a given value, say 10. one way to do this is to traverse the entire list. but its sorted. so I should be able to do faster. – Suraj Nov 12 '10 at 17:49
  • why don't you query the collection using linq ? – Giorgio Minardi Nov 12 '10 at 17:50
  • 1
    because linq is slow. it doesn't take advantage of the fact that the list is sorted. – Suraj Nov 12 '10 at 17:51
  • btw, I could use LINQs TakeWhile, but I want to find values faster than that. – Suraj Nov 12 '10 at 17:53
  • @SFun28: Because it's trivial. Use a binary search. Any time you have a sorted list, binary search should come to mind. – jason Nov 12 '10 at 18:13
  • @Jason: don't be too hard... ;) IMO he knows a binary search fits his needs, but he asked to be sure and to know if there's something already implemented in .NET... – digEmAll Nov 12 '10 at 18:33
  • @SFun28, the algorithm you accept it as answer is O(n) – Saeed Amiri Nov 13 '10 at 18:50

1 Answers1

2

If you mean something like the good-old lower_bound/upper_bound functions on C++ map<>, AFAIK there's nothing built-in in C#.
On List<T> there's a BinarySearch method implemented, but it works on exact matching only.

Anyway, you can easily implement it by yourself, peraphs using the code in this question as an example:
Is there a Lower Bound function on a SortedList<K ,V>?

Community
  • 1
  • 1
digEmAll
  • 56,430
  • 9
  • 115
  • 140
  • I think that's gonna work! I'll respond back once I've implemented. thanks for the pointer!!! – Suraj Nov 12 '10 at 18:02