为什么有List <T> .BinarySearch(...)？

Question

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

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

Answer 1

我注意到除了其他正确答案之外,二进制搜索难以正确编写.有很多极端情况和一些棘手的整数运算.由于二进制搜索显然是一种常见的操作上排序的列表中,BCL团队通过正确地写入二进制搜索算法做了世界一个服务一次,而不是鼓励客户都写自己的二进制搜索算法; 这些客户编写的大量算法都是错误的.

即使是伟大的图书馆设计师也错了:http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html (10认同)
*BCL 团队通过一次正确编写二分搜索算法为全世界提供了服务，而不是鼓励客户都编写自己的二分搜索算法*——嗯，不。如果您有数组或列表以外的其他东西......比如说，一个 Collection<T> ......你就不走运了。其他“团队”做一些明智的事情，并提供一个外部*算法*，可以对任何可索引的序列进行操作。 (2认同)

Answer 2

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

库设计需要妥协 - .NET设计人员选择在两个阵列上提供二进制搜索功能和C#中的列表,因为他们可能觉得(就像我这样)这些是有用的和常见的操作,选择使用它们的程序员理解他们的先决条件(在命令列表之前),在调用它们之前.

List<T>使用其中一个Sort()重载对它进行排序很容易.如果您觉得需要一个gaurantees排序的不变量,您可以随时使用SortedList<TKey,TValue>或SortedSet<T>替代.

Answer 3

BinarySearch不仅使在某种意义上List<T>被排序,就像IList<T>.Add才有意义,对于IList<T>与IsReadOnly = false.这很麻烦,但它只是需要处理的事情:有时候功能X依赖于标准Y.Y并不总是正确的事实并不会使X无用.

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

然后,你可以随时写自己的(或复制别人的).

Answer 4

其他人指出,这BinarySearch对排序非常有用List<T>.但是,它并不真正属于List<T>,因为任何具有C++ STL经验的人都会立即认出来.

随着最近的C#语言开发,定义排序列表(例如ISortedList<T> : IList<T>)和定义BinarySearch(等)的概念作为该接口的扩展方法更有意义.这是一种更清洁,更正交的设计.

我已经开始将其作为Nito.Linq库的一部分.我预计第一个稳定版本会在几个月内发布.

关键是C++ STL支持*正交性*.`vector`没有名为`binary_search`的方法; 相反,`binary_search`可以应用于任何随机访问迭代器,例如`vector`提供的迭代器.将相同的概念应用于C#BCL:`List <T>`不应该提供`BinarySearch`; 也不应该`IList <T>`.它应该是任何`IList <T>`的扩展方法(从而实现`BinarySearch`算法在任何随机访问迭代器/容器上的正交性).(续). (4认同)