.net4 BinarySearch in a sorted List

Question

I want to use the binary search option on a sorted list in c# 4.0. I have been looking at older binary searches:

How would I search a range of ranged values using C#

I would like some help in how I would do a range search between two dates using the binarySearch. I have a list which has many dates and I want to quickly search through this large list between two dates and return the found items if there is any. I though a binary search would be quick as it will quickly get rid of unnecessary comparisons as it is sorted.

msdn.microsoft.com/en-us/library/system.array.binarysearch.aspx — L.B
– L.B, Commented Aug 3, 2012 at 16:06
I voted to close this. You're showing no effort as to what you have tried or where you're stuck. Instead you're just asking for code. — nawfal
– nawfal, Commented Jul 16, 2014 at 8:16

vcRobe · Accepted Answer · 2012-08-03 17:01:11Z

1

Assuming your list is List and your dates are DateTime you can do a List.BinarySearch(...) in this way

List<DateTime> l;
int startIndex = l.BinarySearch(beginDate);
int endIndex = l.BinarySearch(endDate);

At this point you've the range of dates between beginDate and endDate. Now you can get them iterating between the two indexes.

If you want to find the closest date in case the exact date was not found then you can't perform a binary search. In that case you've to re-implement your data structure (in your case your List must be replaced by some powerful structure) to support a range search algorithm that consist of a binary search tree where you will store each year and each node will contain a new binary search tree that will contain all the month belonging to that year now each node will contain a new binary search tree that will contain all the days of that month and so on.

edited Aug 3, 2012 at 17:01

answered Aug 3, 2012 at 16:20

vcRobe

1,8014 gold badges20 silver badges37 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

L.B Over a year ago

What about when beginDate doesn't exist in the list. i.e when it differs in hours? what should OP do when index is negative?

vcRobe Over a year ago

That depends on what you wanna do. If the index is -1 that means that the beginDate doesn't exist so you can show a message box saying that the beginDate was not found or in case the beginDate or endDate are not found you can perform a "find nearest"

L.B Over a year ago

When you do a range search, you will probably not get an exact match. Since DateTime comparison requires an equality even in seconds. Therefore getting an negative index is normal case, and should be handled in the code, not by giving a message. I think your answer should include all of these.

vcRobe Over a year ago

@L.B i've edited the original answer explaining you how to do the find nearest. If you have any doubt please let me know

L.B Over a year ago

I would expect you to say "if you get a negative index, say startIndex, then you can use ~startIndex as an offset to start the search."

|

Nicholas Carey · Accepted Answer · 2012-08-03 18:30:34Z

1

Assumptions:

You have a collection, an ordered list or array of a given type T.
Said collection is a bag (duplicates are allowed) and not a set (unique items).

You need to

Do a binary search to find an item meeting your your "from" criteria, the lower bound.

Since this is a binary search and you have a bag rather than a set, you are not guaranteed that this is the first item in the collection meeting the from criteria. That means that you need to...
Back up to the first item matching the "from" criteria. This is a sequential operation.

At this point, you have the starting point for your iteration. All you have to do is iterate sequentially over the collection from this point...
while the "thru" criteria, the upper bound condition is true.

This might suggest the use of a custom comparer for both the upper and lower bound tests.

It might also suggest a solution in the form of a LINQy extension method.

Good Luck!

edited Aug 3, 2012 at 18:30

answered Aug 3, 2012 at 17:34

Nicholas Carey

75.1k16 gold badges96 silver badges138 bronze badges

1 Comment

nawfal Over a year ago

Not sure if OP has a bag or set. If he means SortedList then it doesn't allow duplicates.

Collectives™ on Stack Overflow

.net4 BinarySearch in a sorted List

2 Answers 2

7 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

7 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related