Dan*_*ner 37 .net generics interface list binary-search
简单的问题 - 给定一个IList<T>如何在不自己编写方法的情况下执行二进制搜索,而不将数据复制到具有内置二进制搜索支持的类型.我目前的状况如下.
List<T>.BinarySearch() 不是会员 IList<T>ArrayList.Adapter()方法List<T>IList<T>不继承IList,因此使用ArrayList.Adapter()是不可能的我倾向于认为使用内置方法是不可能的,但我无法相信BCL/FCL中缺少这样的基本方法.
如果不可能,谁可以提供最短,最快,最智能或最美丽的二进制搜索实现IList<T>？
UPDATE
我们都知道在使用二进制搜索之前必须对列表进行排序,因此您可以假设它是.但我认为(但没有验证)排序是同样的问题 - 你如何排序IList<T>？
结论
似乎没有内置二进制搜索IList<T>.可以使用First()和OrderBy()LINQ方法进行搜索和排序,但它可能会受到性能影响.自己实现它(作为扩展方法)似乎是你能做到的最好的.
ang*_*son 32
我怀疑在.NET中有一个通用的二进制搜索方法,除了一些存在于某些基类中(但显然不在接口中),所以这是我的通用目的.
public static Int32 BinarySearchIndexOf<T>(this IList<T> list, T value, IComparer<T> comparer = null)
{
if (list == null)
throw new ArgumentNullException(nameof(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 ~lower;
}
这当然假定有问题的列表已经按照比较器将使用的相同规则进行了排序.
dev*_*zer 31
我喜欢扩展方法的解决方案.但是,有点警告是有序的.
这实际上是Jon Bentley从他的书"编程珍珠"(Programming Pearls)中的实现,它从一个未被发现20年左右的数字溢出错误中谦虚地受到了影响.如果IList中有大量项目,则(上面+下面)可以溢出Int32.对此的解决方案是使用减法来稍微改变中间计算; 中=低+(上 - 下)/ 2;
Bentley还在Programming Pearls中警告说,虽然二进制搜索算法于1946年发布,但第一个正确的实现直到1962年才发布.
http://en.wikipedia.org/wiki/Binary_search#Numerical_difficulties
Ant*_*bry 30
这是我的Lasse代码版本.我发现能够使用lambda表达式来执行搜索很有用.在对象列表中搜索时,它只允许传递用于排序的键.使用IComparer的实现很容易从这个实现中获得.
我也喜欢在找不到匹配时返回〜更低.Array.BinarySearch会这样做,它允许您知道应该在哪里插入您搜索的项目以保持排序.
/// <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);
}
我一直在努力解决这个问题。特别是MSDN中指定的边缘情况的返回值：http : //msdn.microsoft.com/zh-cn/library/w4e7fxsh.aspx
我现在已经从.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规范，这可以通过可行的解决方案一劳永逸地解决该问题。