List<T>.BinarySearch
if you don't want to use the default comparer of T
, needing to go and create a new class that implements IComparer<T>
. Seems overly messy to require a whole new class just to do the binary search.So I did a little research to see if there was a way around it and found this Jon Skeet answer (obviously) on StackOverflow. It gives a nice generic class that we can instantiate with a
Comparison
object and pass that into the BinarySearch
method. I extended Jon's answer to take a lambda expression instead, much like you can do with List.Sort
.public static class ListExtensions { public static int BinarySearch<T>(this List<T> list, T item, Func<T, T, int> compare) { return list.BinarySearch(item, new ComparisonComparer<T>(compare)); } } public class ComparisonComparer<T> : IComparer<T> { private readonly Comparison<T> comparison; public ComparisonComparer(Func<T, T, int> compare) { if (compare == null) { throw new ArgumentNullException("comparison"); } comparison = new Comparison<T>(compare); } public int Compare(T x, T y) { return comparison(x, y); } }Usage:
List<SomeType> list; // ... Fill the list ... list.Sort((a, b) => a.IntProp.CompareTo(b.IntProp)); var item = list[34]; int index = list.BinarySearch(item, (a, b) => a.IntProp.CompareTo(b.IntProp)); // index == 34
Other handy extensions
Evaluate equality without a second object
public static int BinarySearch<T>(this List<T> list, Func<T, int> compare) where T : class { Func<T, T, int> newCompare = (a, b) => compare(a); return list.BinarySearch((T)null, newCompare); } // Usage: int i = list.BinarySearch(a => a.IntProp == 1);
Return an object
public static T BinarySearchOrDefault<T>(this List<T> list, T item, Func<T, T, int> compare) { int i = list.BinarySearch(item, compare); if (i >= 0) return list[i]; return default(T); } // Usage: SomeType obj = list.BinarySearchOrDefault(item, (a, b) => a.IntProp.CompareTo(b.IntProp));
Search for multiple matches
This extension will perform the binary search and then scan above and below the matching index for any other objects matching the compareFunc
. This function will run in O(1) best case (middle of list), O(log n) average case and O(n) worst case (the entire list matches).
public static List<int> BinarySearchMultiple<T>(this List<T> list, T item, Func<T, T, int> compare) { var results = new List<int>(); int i = list.BinarySearch(item, compare); if (i >= 0) { results.Add(i); int below = i; while (--below >= 0) { int belowIndex = compare(list[below], item); if (belowIndex < 0) break; results.Add(belowIndex); } int above = i; while (++above < list.Count) { int aboveIndex = compare(list[above], item); if (aboveIndex > 0) break; results.Add(aboveIndex); } } return results; } // Usage: List<SomeType> matches = list.BinarySearchMultiple(item, (a, b) => a.IntProp.CompareTo(b.IntProp));