37
|
Daniel Brückner Pradip · 技术社区 · 15 年前 |
1
39
我怀疑在.NET中是否存在这样的通用二进制搜索方法,除了某些基类中存在的方法(但显然不存在于接口中),所以这里是我的通用方法。
当然,这假设所讨论的列表已经按照比较器将使用的相同规则进行了排序。 |
2
35
这是我的Lasse代码版本。我发现能够使用lambda表达式来执行搜索非常有用。在对象列表中搜索时,它只允许传递用于排序的键。使用IComparer的实现基本上就是从这个实现派生出来的。 我也喜欢在找不到匹配项时返回~lower。Array.BinarySearch执行此操作,它允许您知道您搜索的项目应该插入到何处,以便保持顺序。
|
3
34
这实际上是Jon Bentley在其著作《编程珍珠》(Programming Pearls)中的实现,它受到了一个20年左右未被发现的数字溢出错误的影响。如果IList中有大量项,则(上+下)会溢出Int32。解决这个问题的一个办法是,用减法来做中间的计算,方法稍有不同;中间=下部+(上部-下部)/2; Bentley在《Pearls编程》中还警告说,虽然二进制搜索算法于1946年发布,第一个正确的实现直到1962年才发布。 http://en.wikipedia.org/wiki/Binary_search#Numerical_difficulties |
4
5
一段时间以来,我一直在努力把这件事做好。特别是MSDN中规定的边缘情况的返回值: http://msdn.microsoft.com/en-us/library/w4e7fxsh.aspx 我现在从.NET 4.0复制了ArraySortHelper.InternalBinarySearch(),并出于各种原因制作了自己的风格。
这应该适用于所有.NET类型。到目前为止,我已经尝试了int、long和double。 实施:
单元测试:
希望通过一个工作实现一次性解决问题,至少根据MSDN规范。 |
5
4
在搜索二进制文件时会遇到一些问题
我认为你最好的选择是创造一个新的
|
6
3
请注意,下面Antoine提供的实现中有一个bug:搜索大于列表中任何项的项时。返回值应为~lower而不是~middle。反编译方法ArraySortHelper.InternalBinarySearch(mscorlib)以查看框架实现。 |
7
2
如果您需要一个现成的二进制搜索实现
|
8
2
你可以用
|
9
-1
|
10
-1
如果可以使用.NET 3.5,则可以使用内置Linq扩展方法:
然而,对于Andrew Hare的解决方案,这实际上只是一种稍微不同的方式,并且只有在您从同一个有序列表中多次搜索时才真正有用。 |
11
-3
|
danial · 如何在多个字符串的每个位置找到最频繁的字符 1 年前 |
shekharsabale · 从列表元素捕获子字符串 2 年前 |
The Great · 拆分并存储数据帧,但名称基于特定列中的唯一值 2 年前 |
Klimt865 · Python中的列表列表 2 年前 |
Klimt865 · 在Python中将数组列表转换为列表列表 2 年前 |