如何在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,但它可能会带来性能问题。 自己实现(作为扩展方法)似乎是你能做的最好的。

11 Solutions collect form web for “如何在IList <T>上执行二进制search?”

我怀疑在.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。

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

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

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

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

这是我的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); } 

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

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

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

我一直在努力争取一段时间的这个权利。 特别是在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规范。

如果您需要现成的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> { // ... } 

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

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

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

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

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

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

  • 文本search虽然Xcode中的所有.xib文件?
  • 如何在网站中实现searchfunction?
  • Elasticsearch中的碎片和副本
  • 如何计算二进制search的复杂性
  • 在Android操作栏中设置SearchView的样式
  • VIM,增量search:如何跳到下一个结果并突出显示?
  • searchGithub项目中的代码
  • 如何search存储库中的所有Git和Mercurial提交某个string?