私はしばらくこの権利を得ることに苦労しています。特に、MSDNで指定されているようなエッジケースの戻り値：
.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の仕様に従って、実用的な実装で問題を解決することを望んでいます。
古いデータに対してバイナリ検索を実行することはできません。適切にソートされていて、最初に重複がなくてはなりません。 –
リストがソートされていると仮定できます。 –
オブジェクトの基本的なタイプを知っていますか？リストは、SortメソッドとBinarySearchメソッドを提供しません。 –