私はこれを正しくするのにしばらく苦労してきました。特に、MSDNで指定されているエッジケースの戻り値：http：//msdn.microsoft.com/en-us/library/w4e7fxsh.aspx
ArraySortHelper.InternalBinarySearch（）を.NET 4.0からコピーし、さまざまな理由で独自のフレーバーを作成しました。
使用法：
var numbers = new List<int>() { ... };
var items = new List<FooInt>() { ... };
int result1 = numbers.BinarySearchIndexOf(5);
int result2 = items.BinarySearchIndexOfBy(foo => foo.bar, 5);
これは、すべての.NETタイプで機能するはずです。私はこれまでint、long、doubleを試しました。
実装：
public static class BinarySearchUtils
{
public static int BinarySearchIndexOf<TItem>(this IList<TItem> list,
TItem targetValue, IComparer<TItem> comparer = null)
{
Func<TItem, TItem, int> compareFunc =
comparer != null ? comparer.Compare :
(Func<TItem, TItem, int>) Comparer<TItem>.Default.Compare;
int index = BinarySearchIndexOfBy(list, compareFunc, targetValue);
return index;
}
public static int BinarySearchIndexOfBy<TItem, TValue>(this IList<TItem> list,
Func<TItem, TValue, int> comparer, TValue value)
{
if (list == null)
throw new ArgumentNullException("list");
if (comparer == null)
throw new ArgumentNullException("comparer");
if (list.Count == 0)
return -1;
// Implementation below copied largely from .NET4
// ArraySortHelper.InternalBinarySearch()
int lo = 0;
int hi = list.Count - 1;
while (lo <= hi)
{
int i = lo + ((hi - lo) >> 1);
int order = comparer(list[i], value);
if (order == 0)
return i;
if (order < 0)
{
lo = i + 1;
}
else
{
hi = i - 1;
}
}
return ~lo;
}
}
ユニットテスト：
[TestFixture]
public class BinarySearchUtilsTest
{
[Test]
public void BinarySearchReturnValueByMsdnSpecification()
{
var numbers = new List<int>() { 1, 3 };
// Following the MSDN documentation for List<T>.BinarySearch:
// http://msdn.microsoft.com/en-us/library/w4e7fxsh.aspx
// The zero-based index of item in the sorted List(Of T), if item is found;
int index = numbers.BinarySearchIndexOf(1);
Assert.AreEqual(0, index);
index = numbers.BinarySearchIndexOf(3);
Assert.AreEqual(1, index);
// otherwise, a negative number that is the bitwise complement of the
// index of the next element that is larger than item
index = numbers.BinarySearchIndexOf(0);
Assert.AreEqual(~0, index);
index = numbers.BinarySearchIndexOf(2);
Assert.AreEqual(~1, index);
// or, if there is no larger element, the bitwise complement of Count.
index = numbers.BinarySearchIndexOf(4);
Assert.AreEqual(~numbers.Count, index);
}
}
私は自分のコードからこれを切り取ったので、箱から出してうまくいかない場合はコメントしてください。
少なくともMSDNの仕様によれば、これで実装が機能することで問題が解決することを願っています。