Ever have trouble finding things?

This is just a quick code snippet to quickly find the nearest item from a generic list.  It leverages the .NET BinarySearch function, and it also uses the new Extension methods functionality of .NET 3.5 (Visual Studio 2008).

Here’s the extension in its entirety:

public static class BinarySearchExtension
{
    // Computes a distance between the query and a given object.
    public delegate double DistanceFunction<T>(T item);

    // Finds the nearest item to the query item in a sorted list.
    public static int BinarySearchNearest<T>( 
        this List list, T query, 
        DistanceFunction distFunc) {

        int n = list.Count,
            i = ~list.BinarySearch(query); /* O(log(n)) */

        return 
            (i < 0) ? ~i : /* query (q) was in the list */
            (i < 1) ?  0 : /* q < [0] */
            (i == n) ? n - 1 : /* q > [n-1] */ 
            Math.Abs(distFunc(list[i])) < /* [i] < q < [i-1] */
            Math.Abs(distFunc(list[i - 1])) ?
                i : i - 1; /* return the closest  */
    }
}


Here’s an example of using it to search a list of dates:

List<DateTime> times = new List<DateTime>();
times.Add(DateTime.Parse(“8/16/2007?));
times.Add(DateTime.Parse(“7/7/2007?));

times.Sort(); /* Must be sorted before BinarySearch */

int i = times.BinarySearchNearest(DateTime.Now,
        /* distance: hours between now and t */
        t => t.Subtract(DateTime.Now).TotalHours);

DateTime nearest = times[i]; /* nearest is 8/16/2007 */

I have mixed feelings about extensions. They are clean and messy at the same time — clean because you can, with very little code, add new functionality to old classes (even those that you didn’t write). Unfortunately, because the extensions are separated from the classes they concern, it could easily set up a messy dependency situation. For many projects, I think a good practice is to keep all of your extensions localized together in one assembly.