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 2 1663
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]
- mv*@spam.guard.caspershouse.com
"The One We Call 'Dave'" <gh****@englewood.com> wrote in message
news:G8******************************@giganews.com ... 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
Beautiful, thanks!
"Nicholas Paldino [.NET/C# MVP]" <mv*@spam.guard.caspershouse.com> wrote in
message news:u9**************@TK2MSFTNGP10.phx.gbl... 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] - mv*@spam.guard.caspershouse.com
"The One We Call 'Dave'" <gh****@englewood.com> wrote in message news:G8******************************@giganews.com ...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
This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Neal D. Becker |
last post by:
I need a fairly small lookup table, and I'm wondering which data python data
structure would be fastest. I could use a list, tuple, dictionary, numeric
array, or maybe plain python array. The...
|
by: tommazzo |
last post by:
Hi!
I'm looking for a way to find the position of a certain pattern within a
string. On my search on the internet I've come accross various algorithms
such as Knuth-Morris-Pratt and Boyer-Moore...
|
by: PWalker |
last post by:
Hi, I have written code that I would like to optimize. I need to push it to
the limit interms of speed as the accuracy of results are proportional to
runtime.
First off, would anyone know any...
|
by: yee young han |
last post by:
I need a fast data structure and algorithm like below condition.
(1) this data structure contain only 10,000 data entry.
(2) data structure's one entry is like below
typedef struct _DataEntry_...
|
by: microsoft |
last post by:
I have a very "flat" doc structure like this
<root>
<one>
<two>
<three>
...
n <=100
</root>
|
by: Roy Gourgi |
last post by:
Hi,
I am new to C#. I have the same time scheduling program written in C++ and
it is 5 times faster than my version in C#.
Why is it so slow as I thought that C# was only a little slower than...
|
by: Peter Schmitz |
last post by:
Hi again,
I just need to write the following function to search in a binary buffer for
a given pattern:
BOOL CheckBufferForPattern(BYTE *buffer,int bufferlen,BYTE *pattern, int
patternlen,...
|
by: The One We Call 'Dave' |
last post by:
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...
|
by: pj |
last post by:
Hi,
I 'm currently writing a program that performs transliteration (i.e.,
converts greek text written using the english alphabet to "pure" greek
text using the greek alphabet) as part of my...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and...
| |