14

我正在查看 List 并且看到一个带有一些重载的 BinarySearch 方法，我不禁想知道在 List 中使用这样的方法是否有意义？

除非列表已排序，否则我为什么要进行二进制搜索？如果列表没有排序，调用该方法只会浪费 CPU 时间。在 List 上使用该方法有什么意义？

4

9 回答 9

24

我注意到除了其他正确答案之外，二进制搜索很难正确编写。有很多极端情况和一些棘手的整数运算。由于二分查找显然是排序列表上的常见操作，因此 BCL 团队通过正确编写一次二分查找算法而不是鼓励客户都编写自己的二分查找算法来为世界提供服务；这些客户编写的算法中有很大一部分是错误的。

于 2010-07-15T14:19:51.273 回答
20

排序和搜索是列表上两个非常常见的操作。通过不在常规列表上提供二进制搜索来限制开发人员的选择是不友好的。

库设计需要妥协——.NET 设计人员选择在 C# 中对数组和列表提供二进制搜索功能，因为他们可能（和我一样）觉得这些是有用且常见的操作，选择使用它们的程序员了解他们的先决条件（即列表是有序的）在调用它们之前。

List<T>使用其中一个Sort()重载对 a 进行排序很容易。如果你觉得你需要一个保证排序的不变量，你总是可以使用SortedList<TKey,TValue>orSortedSet<T>代替。

于 2010-07-15T13:48:55.540 回答
9

BinarySearch仅对List<T>已排序的 a 有意义，就像IList<T>.Add仅对IList<T>with有意义一样IsReadOnly = false。这很混乱，但这只是需要处理的事情：有时功能 X 取决于标准 Y。Y 并不总是正确的事实并不会使 X 无用。

现在，在我看来，令人沮丧的是.NET 没有任何实现的通用 Sort和BinarySearch方法（例如，作为扩展方法）。如果是这样，我们可以轻松地对任何提供随机访问的非只读集合中的项目进行排序和搜索。 IList<T>

再说一次，你总是可以自己写（或复制别人的）。

于 2010-07-15T14:08:19.320 回答
6

其他人指出，BinarySearch在 sorted 上非常有用List<T>。不过，它并不真正属于 . List<T>，因为任何具有 C++ STL 经验的人都会立即意识到这一点。

随着最近 C# 语言的发展，定义排序列表（例如 ）的概念并将（等ISortedList<T> : IList<T>）定义为该接口的扩展方法更有意义。BinarySearch这是一种更简洁、更正交的设计。

作为Nito.Linq库的一部分，我已经开始这样做了。我预计第一个稳定版本将在几个月后发布。

于 2010-07-15T14:04:55.803 回答
3

是的，但是 List 也有 Sort() 方法，所以你可以在 BinarySearch 之前调用它。

于 2010-07-15T13:46:03.563 回答
3

搜索和排序是算法原语。标准库有快速可靠的实现是有帮助的。否则，开发人员会浪费时间重新发明轮子。

但是，在 .NET Framework 的情况下，不幸的是，算法的特定选择恰好使它们的用处不如预期。在某些情况下，它们的行为没有定义：

  1. List<T>.BinarySearch如果 List 包含多个具有相同值的元素，则该方法仅返回其中一个，并且它可能返回任何一个，不一定是第一个。

  2. List<T>此实现执行不稳定的排序；也就是说，如果两个元素相等，它们的顺序可能不会被保留。相反，稳定排序保留了相等元素的顺序。

真可惜，因为有一些确定性算法也一样快，而且这些算法作为构建块会更有用。值得注意的是，Python、Ruby 和 Go 中的二进制搜索算法都找到了第一个匹配元素。

于 2014-02-19T15:34:26.427 回答
2

我同意在未排序的列表上调用 BinarySearch 是完全愚蠢的，但如果你知道你的大列表已排序，那就完美了。

在检查流中的项目是否存在于（或多或少）100,000 个或更多项目的静态列表中时，我使用了它。

对列表进行二进制搜索比执行列表查找要快 ORDERS 数量级。查找比数据库查找要快许多数量级。

我是有道理的，我很高兴它在那里（如果不是这样的话，实现它并不是火箭科学）。

于 2010-07-15T13:56:36.463 回答
1

也许另一点是数组可以同样未排序。所以理论上，在数组上使用 BinarySearch 也可能是无效的。

但是，与高级语言的所有功能一样，它们需要由对数据有理性和理解的人来应用，否则它们会失败。当然，可以应用一些交叉检查，我们可以有一个标记为“IsSorted”的标志，否则它会在二进制搜索中失败，但是......

于 2017-08-18T14:02:15.973 回答
0

一些伪代码：

if List is sorted
   use the BinarySearch method
else if List is not sorted and you think sorting it is "waste of CPU time"
   use a different algorithm that is more suitable and efficient
于 2017-09-26T21:04:44.457 回答