C# binarysearch a list<T> by a member of T

Question

I have a baseclass Event with a DateTime member TimeStamp. Lots of other event-classes will derive from this.

I want to be able to search a list of events fast, so I'd like to use a binary search.

(The list-data is sorted on timestamp, but there might be duplicate timestamps for events that occurred simultaneously)

So I started out writing something like this :

public class EventList<T> : List<T> where T : Event
{
   private IComparer<T> comparer = (x, y) => Comparer<DateTime>.Default.Compare(x.TimeStamp, y.TimeStamp);

   public IEnumerable<T> EventsBetween(DateTime inFromTime, DateTime inToTime)
   {
       // Find the index for the beginning. 
       int index = this.BinarySearch(inFromTime, comparer);

       // BLAH REST OF IMPLEMENTATION
   }
}

The problem is that the BinarySearch only accepts T (so - an Event type) as parameter, while I want to search based on a member of T - the TimeStamp.

What would be a good way to approach this ?

Answer 1

I think that you already are on the right way with your comparer function. It compares two T's by comparing the dates of them.

To handle the inFromTime parameter to BinarySearch you can create a dummy Event which has the correct TimeStamp and pass that dummy to BinarySearch.

Also, just to make sure: Is the list sorted on the time field? Otherwise binarysearch won't work.

Edit

This problem is more complex than I first thought. A solution that would help you is:

• Make an adapter class which exposes your EventList as an IList.
• Use a BinarySearch extension method on IList to do the search.

Unfortunately there is no built in BinarySearch extension method, so you will have to write your own. In case you write your own search it might not be worth the extra effort to put it in an extension method. In that case just implementing a custom BinarySearch algorithm yourself in your EventList class is probably the best you can do.

Another option would be if there was a form of BinarySearch that accepted a delegate that extracts the relevant key from T, but that is not available either.