Here you go - a C# 3 version amenable to binary-search on a sub-
property; actually it should work in C# 2 given a few minor changes,
but anonymous methods aren't as appealing as lambdas, and the
extension methods and improved type inference really help us here...
using System;
using System.Collections.Generic;
class Racer
{
public string Car { get; set; }
}
static class Program
{
static void Main(string[] args)
{
List<Racer> racers = new List<Racer>();
Random rand = new Random(123456);
for (int i = 0; i < 10000; i++)
{ // invent some random data
racers.Add(new Racer { Car = rand.Next().ToString() });
}
// add some known data to look for and sort
racers.Add(new Racer { Car = "12345" });
racers.Sort(r => r.Car);
int index = racers.BinarySearch(r => r.Car, "12345");
}
}
public static class ListExt
{
public static void Sort<TSource, TValue>(this List<TSource> list,
Func<TSource, TValue> selector)
{
list.Sort(new SelectorComparer<TSource, TValue>(selector,
null, false));
}
public static int BinarySearch<TSource, TValue>(this
IList<TSource> list,
Func<TSource, TValue> selector, TValue value)
{
return BinarySearch(list, 0, list.Count, selector, value,
null);
}
public static int BinarySearch<TSource, TValue>(this
IList<TSource> list,
Func<TSource, TValue> selector, TValue value,
IComparer<TValue> comparer)
{
return BinarySearch(list, 0, list.Count, selector, value,
comparer);
}
public static int BinarySearch<TSource, TValue>(this
IList<TSource> list, int index, int length,
Func<TSource, TValue> selector, TValue value)
{
return BinarySearch(list, index, length, selector, value,
null);
}
public static int BinarySearch<TSource, TValue>(this
IList<TSource> list, int index, int length,
Func<TSource, TValue> selector, TValue value,
IComparer<TValue> comparer)
{
if (comparer == null)
{
comparer = Comparer<TValue>.Default;
}
int lowerBound = index;
int upperBound = (index + length) - 1;
while (lowerBound <= upperBound)
{
int compareResult;
int testIndex = lowerBound + ((upperBound - lowerBound) >>
1);
try
{
compareResult =
comparer.Compare(selector(list[testIndex]), value);
}
catch (Exception exception)
{
throw new InvalidOperationException("Comparer failed",
exception);
}
if (compareResult == 0)
{
return testIndex;
}
if (compareResult < 0)
{
lowerBound = testIndex + 1;
}
else
{
upperBound = testIndex - 1;
}
}
return int.MinValue;
}
}
/// <summary>
/// Comparer to sort elements of T based on a projection
/// </summary>
/// <typeparam name="T">Element type</typeparam>
/// <typeparam name="TKey">The projected type (usually a property)</
typeparam>
internal class SelectorComparer<T, TKey> : IComparer<T>
{
private readonly Func<T, TKey> selector;
private readonly IComparer<TKey> comparer;
private readonly bool descending;
/// <summary>
/// Create a new comparer based on a projection
/// </summary>
/// <param name="selector">The projection function to apply to
obtain the key to compare</param>
/// <param name="comparer">The comparer used to compare keys
(defaults if null)</param>
/// <param name="descending">Should the order be considered
ascending or descending?</param>
public SelectorComparer(
Func<T, TKey> selector,
IComparer<TKey> comparer,
bool descending)
{
if (selector == null) throw new
ArgumentNullException("selector");
this.selector = selector;
this.comparer = comparer ?? Comparer<TKey>.Default;
this.descending = descending;
}
int IComparer<T>.Compare(T x, T y)
{
return descending
? comparer.Compare(selector(y), selector(x))
: comparer.Compare(selector(x), selector(y));
}
}
