Flexible Binary Searches

Saturday, February 3, 2007

Suppose you need to perform a binary search under the following conditions:

• You have a strongly typed list, using the generic List<T> class.
• The list is ordered by a member of T. That is, the order is defined by a property of the list's element type, for example, a list of customers might be ordered by the customers' names.
• You want to look up an element in the list, having only a value of the member type; in our example, a customer name.

If you use the BinarySearch method of the List<T> class, you have to provide an object of the element type - forcing you to come up with a dummy object. That's true even if you use a custom comparer - after all, strong typing is the holy grail of generics, isn't it?

Now, in the case of a binary search, we know that every comparison operation compares the search criterion and one element of the list. So we could write a compare method that compares a customer object with a string:

int Compare(Customer customer, string sName)
{
    return customer.Name.CompareTo(sName);
}

But with a generic collection and generic comparers, we're forced to compare customers with customers, and that's it.

One .NET framework solution to this problem is to use the generic SortedList class, which stores values and keys separately, and so carries a bit of overhead. Also, it does not allow duplicate keys.

However, even when using strongly typed generic collections, we can still use a custom binary search method that accepts a compare using multiple types:

int BinarySearch<ValueType, KeyType>(
    IList<ValueType> list,
    KeyType key,
    Callback<int, ValueType, KeyType> comparer // int(ValueType,KeyType);
);

We can then implement the comparison however we see fit; and thanks to the type system, we'll know which paramete is an element from the list, and which is the argument passed to the search:

IList<Customer> list = GetCustomerList();
int idx = BinarySearch<Customer, string>(list, "Henry",
        delegate(Customer value, string key)
        {
            return value.Name.CompareTo(key);
        }
    );
return (idx >= 0 ? list[idx] : null);

This is a similiar approach as the one in the List<T> Find... methods, the difference being that a linear search is used in that case, with simple true/false results from the System.Predicate<T> delegate.

I have added this functionality to the Gregor.Core library, in the Collections.CollectionUtil class.

The new BinarySearch method there has the same behaviour as the List<T>.BinarySearch and Array.BinarySearch<T> methods with regard to non-existing elements: it returns the bitwise complement of the index of the element that is (or would be) positioned after the element to insert, which can then be used as an insertion index.