如何在IList <T>上执行二进制search？

简单的问题 – 给定一个IList<T>你如何执行二进制search，而不用自己编写方法，也不要将数据复制到具有内置二进制search支持的types。 我目前的状态如下。

• List<T>.BinarySearch()不是IList<T>的成员
• List<T>没有等价的ArrayList.Adapter()方法
• IList<T>不从IListinheritance，因此使用ArrayList.Adapter()是不可能的

我倾向于认为用内置的方法是不可能的，但我不能相信BCL / FCL中没有这样一个基本的方法。

如果不可能，谁可以给IList<T>最短，最快，最聪明，最漂亮的二进制search实现？

UPDATE

我们都知道，在使用二分search之前，一个列表必须被sorting，因此您可以假设它是。 但我认为（但没有validation）这是sorting相同的问题 – 你如何sortingIList<T> ？

结论

似乎没有内置的二进制searchIList<T> 。 可以使用First()和OrderBy() LINQ方法进行search和sorting，但它可能会带来性能问题。 自己实现（作为扩展方法）似乎是你能做的最好的。

Answer 1

我怀疑在.NET中有一个通用的二进制search方法，除了在某些基类中存在（但显然不在接口中），所以这是我的通用目的。

 public static Int32 BinarySearchIndexOf<T>(this IList<T> list, T value, IComparer<T> comparer = null) { if (list == null) throw new ArgumentNullException("list"); comparer = comparer ?? Comparer<T>.Default; Int32 lower = 0; Int32 upper = list.Count - 1; while (lower <= upper) { Int32 middle = lower + (upper - lower) / 2; Int32 comparisonResult = comparer.Compare(value, list[middle]); if (comparisonResult == 0) return middle; else if (comparisonResult < 0) upper = middle - 1; else lower = middle + 1; } return -1; } 

这当然假定所讨论的列表已经按照比较器将使用的相同规则进行了sorting。

Answer 2

我喜欢使用扩展方法的解决scheme。 但是，有一点警告是为了。

这实际上是Jon Bentley在他的“Programming Pearls”一书中的实现，它受到20年前未被发现的数值溢出错误的影响。 如果在IList中有大量项目，则（上+下）可能溢出Int32。 解决这个问题的方法是使用减法来进行中间计算。 中间=下+（上 – 下）/ 2;

Bentley在编程珍珠中也警告说，尽pipe二分法searchalgorithm是在1946年发布的，第一个正确的实现直到1962年才发布。

http://en.wikipedia.org/wiki/Binary_search#Numerical_difficulties

Answer 3

这是我的Lasse的代码版本。 我发现能够使用lambdaexpression式来执行search是很有用的。 在对象列表中search时，它只允许传递用于sorting的密钥。 使用IComparer的实现是从这个实例派生出来的。

如果找不到匹配，我也想返回〜更低。 Array.BinarySearch可以做到这一点，它可以让你知道你要search的项目在哪里插入，以保持sorting。

 /// <summary> /// Performs a binary search on the specified collection. /// </summary> /// <typeparam name="TItem">The type of the item.</typeparam> /// <typeparam name="TSearch">The type of the searched item.</typeparam> /// <param name="list">The list to be searched.</param> /// <param name="value">The value to search for.</param> /// <param name="comparer">The comparer that is used to compare the value with the list items.</param> /// <returns></returns> public static int BinarySearch<TItem, TSearch>(this IList<TItem> list, TSearch value, Func<TSearch, TItem, int> comparer) { if (list == null) { throw new ArgumentNullException("list"); } if (comparer == null) { throw new ArgumentNullException("comparer"); } int lower = 0; int upper = list.Count - 1; while (lower <= upper) { int middle = lower + (upper - lower) / 2; int comparisonResult = comparer(value, list[middle]); if (comparisonResult < 0) { upper = middle - 1; } else if (comparisonResult > 0) { lower = middle + 1; } else { return middle; } } return ~lower; } /// <summary> /// Performs a binary search on the specified collection. /// </summary> /// <typeparam name="TItem">The type of the item.</typeparam> /// <param name="list">The list to be searched.</param> /// <param name="value">The value to search for.</param> /// <returns></returns> public static int BinarySearch<TItem>(this IList<TItem> list, TItem value) { return BinarySearch(list, value, Comparer<TItem>.Default); } /// <summary> /// Performs a binary search on the specified collection. /// </summary> /// <typeparam name="TItem">The type of the item.</typeparam> /// <param name="list">The list to be searched.</param> /// <param name="value">The value to search for.</param> /// <param name="comparer">The comparer that is used to compare the value with the list items.</param> /// <returns></returns> public static int BinarySearch<TItem>(this IList<TItem> list, TItem value, IComparer<TItem> comparer) { return list.BinarySearch(value, comparer.Compare); } 

Answer 4

首先，像你提到的那样， List<T>上的BinarySearch方法不是IList<T>接口的成员。 其次，在search之前，您无法对列表进行sorting（您必须执行二进制search才能正常工作）。

我认为你最好的select是创build一个新的List<T> ，对其进行sorting，然后search。 这并不完美，但如果你有一个IList<T>你不需要很多select。

Answer 5

请注意，下面的Antoine提供的实现中存在一个错误：当search一个大于列表中的任何项目的项目时。 返回值应该是〜不低于中等。 反编译方法ArraySortHelper.InternalBinarySearch（mscorlib）来查看框架实现。

Answer 6

我一直在努力争取一段时间的这个权利。 特别是在MSDN中指定的边缘情况的返回值： http : //msdn.microsoft.com/en-us/library/w4e7fxsh.aspx

我现在已经从.NET 4.0中复制了ArraySortHelper.InternalBinarySearch（），并且由于各种原因而创build了自己的风格。

用法：

 var numbers = new List<int>() { ... }; var items = new List<FooInt>() { ... }; int result1 = numbers.BinarySearchIndexOf(5); int result2 = items.BinarySearchIndexOfBy(foo => foo.bar, 5); 

这应该适用于所有的.NETtypes。 我已经尝试过int，长到目前为止。

执行：

 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; } } 

unit testing：

 [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); } } 

我刚刚从我自己的代码中剪掉了这个，所以请评论它是不是开箱即用。

希望能够一劳永逸地解决这个问题，至less根据MSDN规范。

Answer 7

如果您需要现成的IList<T>二进制search实现， Wintellect的Power Collections 有一个 （在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&lt;T&gt;). /// </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> { // ... } 

Answer 8

你可以使用List<T>.BinarySearch(T item) 。 如果要使用自定义比较器，则使用List<T>.BinarySearch(T item, IComparer<T> comparer) 。 看看这个MSDN 链接了解更多细节。

Answer 9

请记住，二进制search对于某些列表实现来说可能效率很低。 例如，对于一个链表，如果你正确地实现了它，那么它是O（n），如果你是天真地实现它，则是O（n log n）。

Answer 10

如果您可以使用.NET 3.5，则可以使用Linq扩展方法中的构build：

 using System.Linq; IList<string> ls = ...; var orderedList = ls.OrderBy(x => x).ToList(); orderedList.BinarySearch(...); 

然而，这实际上只是Andrew Hare的解决scheme的一个稍微不同的方法，而且如果您要从同一个有序列表中多次search，这才真正有用。

Answer 11

请注意，虽然列表和IList没有BinarySearch方法，SortedList。