IList<T>，如何在不自己编写方法的情况下以及不将数据复制到具有内置二进制搜索支持的类型的情况下执行二进制搜索。我当前的状态如下。List<T>.BinarySearch()不是IList<T>的成员ArrayList.Adapter()的ArrayList.Adapter()方法没有与此等效的方法>>List<T>不继承自IList<T>，因此无法使用IList如果不可能，谁可以为ArrayList.Adapter()提供最短，最快，最聪明或最漂亮的二进制搜索实现？
UPDATE
IList<T>？结论
[[0]似乎没有内置的二进制搜索。可以使用IList<T>和IList<T> LINQ方法进行搜索和排序，但是它会带来性能上的损失。自己实现（作为扩展方法）似乎可以做的最好。简单的问题-给定一个IList
，您如何在不自己编写方法的情况下执行二进制搜索，又如何在不支持内置二进制搜索的情况下将数据复制到类型中。我当前的...
First()
当然，这是根据比较器将使用的相同规则，对有关列表进行了排序。
List<T>.BinarySearch(T item, IComparer<T> comparer)
这实际上是乔恩·本特利（Jon Bentley）在他的《 Programming Pearls》一书中的实现，它遭受了一个数值溢出的错误的困扰，该错误在20年左右的时间里未被发现。如果IList中有大量项目，则（upper + lower）可能会溢出Int32。一个解决方案是使用减法来略微不同地进行中间计算。中=下+（上-下）/ 2;
我也想在找不到匹配项时返回〜lower。 Array.BinarySearch做到了这一点，它使您可以知道要搜索的项目应插入到哪里，以保持顺序。
我现在已经从.NET 4.0复制了ArraySortHelper.InternalBinarySearch（）并出于各种原因做出了自己的选择。
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);
}
}
上的IList<T>方法不是BinarySearch接口的成员。其次，您无法在搜索之前对列表进行排序（必须进行二进制搜索才能工作）。我认为您最好的选择是创建一个新的List<T>，对其进行排序，然后进行搜索。它并不完美，但是如果您有IList<T>，则没有太多选择。
Algorithms.cs。如果要使用自定义比较器，请使用/// <summary>
/// Searches a sorted list for an item via binary search. The list must be sorted
/// by the natural ordering of the type (it's implementation of IComparable<T>).
/// </summary>
/// <param name="list">The sorted list to search.</param>
/// <param name="item">The item to search for.</param>
/// <param name="index">Returns the first index at which the item can be found. If the return
/// value is zero, indicating that <paramref name="item"/> was not present in the list, then this
/// returns the index at which <paramref name="item"/> could be inserted to maintain the sorted
/// order of the list.</param>
/// <returns>The number of items equal to <paramref name="item"/> that appear in the list.</returns>
public static int BinarySearch<T>(IList<T> list, T item, out int index)
where T: IComparable<T>
{
// ...
}
。请查看此MSDN List<T>.BinarySearch(T item)了解更多详细信息。