.NET Lookup Algorithm: Which is fastest?

  • Thread starter Thread starter The One We Call 'Dave'
  • Start date Start date
T

The One We Call 'Dave'

I have a list of DateTime objects stored in a collection:

SortedList<DateTime,Object> MyDates=new SortedList<DateTime,Object>();

The dates, which can be accessed via MyDates.Keys, are stored in ascending
order. What is the fastest way to find the MAXIMUM date within 'MyDates'
which is LESS THAN or EQUAL to 12/30/05?

MyDates.ContainsKey() will tell me if the 12/30/05 exists in the list. If,
however, 12/30/05 does NOT exist in the list but 12/29/05 DOES exist in the
list, I'd like 12/29/05 to be returned.

The brute force method of iterating through the entire MyDates.Keys
collection will work of course, but this method strikes me as inefficient
since it's not taking advantage of the fact that the items are in fact
ordered.

The other idea that I came up with is to start looking in the middle of the
list and gradually narrow my search area based upon each 'hit'.

What's the best way to approach this problem? Is there an instance method
that I'm overlooking ?

Dave
 
Dave,

The way I would handle this is to use a modified binary search
algorithm.

You hinted on it in your email, so you kind of know already what you
have to do. Basically, you have a sorted array with N elements. You start
at element N/2 and see if it is a match. If not, and the value you are
looking for is less than the element at N/2, you find the middle point of 0
and N/2, and then continue, over and over.

Fortunately, this is implemented for you in the static BinarySearch
algorithm on the Array class. Additionally, if the value you are looking
for is not found, it will return the bitwise compliment of the index of the
first element greater than your value.

All you have to do is take your sorted keys and then run them through
the BinarySearch method, and it should give you what you want.

Hope this helps.
 
Beautiful, thanks!

Nicholas Paldino said:
Dave,

The way I would handle this is to use a modified binary search
algorithm.

You hinted on it in your email, so you kind of know already what you
have to do. Basically, you have a sorted array with N elements. You
start at element N/2 and see if it is a match. If not, and the value you
are looking for is less than the element at N/2, you find the middle point
of 0 and N/2, and then continue, over and over.

Fortunately, this is implemented for you in the static BinarySearch
algorithm on the Array class. Additionally, if the value you are looking
for is not found, it will return the bitwise compliment of the index of
the first element greater than your value.

All you have to do is take your sorted keys and then run them through
the BinarySearch method, and it should give you what you want.

Hope this helps.


--
- Nicholas Paldino [.NET/C# MVP]
- (e-mail address removed)

The One We Call 'Dave' said:
I have a list of DateTime objects stored in a collection:

SortedList<DateTime,Object> MyDates=new SortedList<DateTime,Object>();

The dates, which can be accessed via MyDates.Keys, are stored in
ascending order. What is the fastest way to find the MAXIMUM date within
'MyDates' which is LESS THAN or EQUAL to 12/30/05?

MyDates.ContainsKey() will tell me if the 12/30/05 exists in the list.
If, however, 12/30/05 does NOT exist in the list but 12/29/05 DOES exist
in the list, I'd like 12/29/05 to be returned.

The brute force method of iterating through the entire MyDates.Keys
collection will work of course, but this method strikes me as inefficient
since it's not taking advantage of the fact that the items are in fact
ordered.

The other idea that I came up with is to start looking in the middle of
the list and gradually narrow my search area based upon each 'hit'.

What's the best way to approach this problem? Is there an instance method
that I'm overlooking ?

Dave
Click to expand...
Click to expand...
 
Back
Top