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

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

UPDATE

### 11 Solutions collect form web for “如何在IList <T>上执行二进制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; }` `

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

` `/// <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); }` `

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

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

` `/// <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> { // ... }` `

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

• 在没有索引的情况下search文件内的string的工具
• 计算文件中的模式出现次数（即使在同一行）
• 如何在记事本++中复制标记的文本
• 从Visual Studiosearch中排除特定的文件
• 如果针是一个arrays，我怎样才能使用in_array？
• 标签，云和search的最佳数据架构（如StackOverflow）？
• 广度优先search在寻找最短path时如何工作？
• Python的re.search和re.match有什么区别？
• 如何用jQuerysearchJSON树
• 有没有可能在GitHub上search特定的文件名？