Skip to content

Instantly share code, notes, and snippets.

@Larry57
Created April 16, 2014 20:57
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Larry57/10932369 to your computer and use it in GitHub Desktop.
Save Larry57/10932369 to your computer and use it in GitHub Desktop.
BinarySearch in a list, using a selector
namespace System.Collections.Generic
{
public static class ListExtensions
{
/// <summary>
/// Do a binary search in a generic list
/// </summary>
/// <typeparam name="T"></typeparam>
/// <typeparam name="U"></typeparam>
/// <param name="tf">list</param>
/// <param name="target">Target</param>
/// <param name="selector">Return the value that should match the target</param>
/// <returns></returns>
public static int BinarySearch<T, U>(this IList<T> tf, U target, Func<T, U> selector)
{
var lo = 0;
var hi = (int)tf.Count - 1;
var comp = Comparer<U>.Default;
while (lo <= hi)
{
var median = lo + (hi - lo >> 1);
var num = comp.Compare(selector(tf[median]), target);
if (num == 0)
return median;
if (num < 0)
lo = median + 1;
else
hi = median - 1;
}
return ~lo;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment