一段时间以来,我一直在努力解决这个问题。特别是 MSDN 中指定的边缘情况的返回值:http: //msdn.microsoft.com/en-us/library/w4e7fxsh.aspx
我现在已经从 .NET 4.0 复制了 ArraySortHelper.InternalBinarySearch() 并出于各种原因制作了自己的风格。
用法:
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 规范。