Created
April 16, 2014 20:57
-
-
Save Larry57/10932369 to your computer and use it in GitHub Desktop.
BinarySearch in a list, using a selector
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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