# May 24, 2010

**Update: Some time after writing this post, I created a project on GitHub for this.**

Here's a problem I'm sure tons of developers have run into, resulting in much frustration.

Say you have a sorted list of some kind, but it's not a `List(T)`

, and it's not an array. In other words, it's an `IList(T)`

that you know is sorted. If you want to search for an item within that list, it makes sense to utilize a binary search, rather than a linear search; but guess what? That doesn't exist in the .NET framework. There's `List(T).BinarySearch`

, and there's `Array.BinarySearch(T)`

, but there's no general `BinarySearch`

(just like there's no general `Sort`

).

One data structure where this proves particularly frustrating is `SortedList(TKey, TValue)`

, because, although `SortedList(TKey, Value)`

*does* have an `IndexOfKey`

method, and this method *is* a binary search, it returns -1 if the value passed isn't found. This basically makes it a crippled version of `Array.BinarySearch(T)`

, which actually returns the **negative bitwise complement** of the "next best" index (that of the first value greater than the value searched for) -- a useful little piece of information that allows you to write code like this:

```
int closestIndex = Array.BinarySearch(myArray, someValue);
if (closestIndex < 0)
closestIndex = ~closestIndex;
```

Now, why do you suppose `IndexOfKey`

is inconsistent with `List(T).BinarySearch`

and `Array.BinarySearch(T)`

? Is it due to some subtle difference in implementation that is necessary for the internal structure of `SortedList(TKey, TValue)`

?

Buh, no. Take a look at the source code for the `IndexOfKey`

method using Reflector, and what you'll find is this peculiar little bit of code:

```
int num = Array.BinarySearch<TKey>(this.keys, 0, this._size, key, this.comparer);
if (num < 0)
{
return -1;
}
return num;
```

**Seriously**? You're telling me `IndexOfKey`

*actually uses Array.BinarySearch(T)*, and just refuses to return the same value?

This is NOT ACCEPTABLE (to me, anyway). Thankfully, Reflector allows us to take a gander at the implementation of `Array.BinarySearch(T)`

as well, which can be refitted to work on any `IList(T)`

, no problem. (Believe me when I say this is **extremely preferable** to implementing one's own binary search... especially when you see how simple this implementation is.)

**Behold, a generic BinarySearch method that will work on any IList(T), based on Microsoft's own Array.BinarySearch(T) implementation:**

(I've also included the obvious overloads.)

```
public static int BinarySearch<T>(this IList<T> list, int index, int length, T value, IComparer<T> comparer) {
if (list == null)
throw new ArgumentNullException("list");
else if (index < 0 || length < 0)
throw new ArgumentOutOfRangeException(
(index < 0) ? "index" : "length"
);
else if (list.Count - index < length)
throw new ArgumentException();
int lower = index;
int upper = (index + length) - 1;
while (lower <= upper) {
int adjustedIndex = lower + ((upper - lower) >> 1);
int comparison = comparer.Compare(list[adjustedIndex], value);
if (comparison == 0)
return adjustedIndex;
else if (comparison < 0)
lower = adjustedIndex + 1;
else
upper = adjustedIndex - 1;
}
return ~lower;
}
public static int BinarySearch<T>(this IList<T> list, T value, IComparer<T> comparer) {
return list.BinarySearch(0, list.Count, value, comparer);
}
public static int BinarySearch<T>(this IList<T> list, T value) where T : IComparable<T> {
return list.BinarySearch(value, Comparer<T>.Default);
}
```

Feel free to add this code to any static helper class you like. I know I will.