为什么会有 List.BinarySearch(...)？
我正在查看 List，看到一个带有一些重载的 BinarySearch 方法，我不禁想知道在 List 中使用类似的方法是否有意义？
除非列表已排序，否则为什么我要进行二分搜索？如果列表没有排序，调用该方法只会浪费 CPU 时间。将这个方法放在 List 上有什么意义？
I'm looking at List and I see a BinarySearch method with a few overloads, and I can't help wondering if it makes sense at all to have a method like that in List?
Why would I want to do a binary search unless the list was sorted? And if the list wasn't sorted, calling the method would just be a waste of CPU time. What's the point of having that method on List?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（9）
我注意到，除了其他正确答案之外，二分搜索很难正确编写。有很多极端情况和一些棘手的整数算术。由于二分搜索显然是排序列表上的常见操作，因此 BCL 团队通过正确编写一次二分搜索算法来为世界提供服务，而不是鼓励所有客户都编写自己的二分搜索算法；这些客户编写的算法中有很大一部分是错误的。
I note in addition to the other correct answers that binary search is surprisingly hard to write correctly. There are lots of corner cases and some tricky integer arithmetic. Since binary search is obviously a common operation on sorted lists, the BCL team did the world a service by writing the binary search algorithm correctly once rather than encouraging customers to all write their own binary search algorithm; a significant number of those customer-authored algorithms would be wrong.
排序和搜索是列表上两种非常常见的操作。通过不在常规列表上提供二分搜索来限制开发人员的选项是不友好的。
库设计需要妥协 - .NET 设计者选择在 C# 中的数组和列表上提供二分搜索功能，因为他们可能觉得（正如我所做的那样）这些是有用且常见的操作，选择使用它们的程序员在调用它们之前了解它们的先决条件（即列表是有序的）。
使用
Sort()重载。如果您觉得需要保证排序的不变式，则可以随时使用SortedList或SortedSet相反。Sorting and searching are two very common operations on lists. It would be unfriendly to limit a developer's options by not offering binary search on a regular list.
Library design requires compromises - the .NET designers chose to offer the binary search function on both arrays and lists in C# because they likely felt (as I do) that these are useful and common operations, and programmers who choose to use them understand their prerequisites (namely that the list is ordered) before calling them.
It's easy enough to sort a
List<T>using one of theSort()overloads. If you feel that you need an invariant that gaurantees sorting, you can always useSortedList<TKey,TValue>orSortedSet<T>instead.BinarySearch仅对已排序的List有意义，就像IList.Add 仅对有意义>IList与IsReadOnly = false。这很混乱，但它只是需要处理的事情：有时功能 X 取决于标准 Y。Y 并不总是正确的事实并不意味着 X 毫无用处。现在，在我看来，令人沮丧的是 .NET 没有用于 通用
Sort和BinarySearch方法。 em>任何IList实现（例如，作为扩展方法）。如果确实如此，我们就可以轻松地对提供随机访问的任何非只读集合中的项目进行排序和搜索。话又说回来，您始终可以编写自己的（或 复制别人的）。
BinarySearchonly makes sense on aList<T>that is sorted, just likeIList<T>.Addonly makes sense for anIList<T>withIsReadOnly = false. It's messy, but it's just something to deal with: sometimes functionality X depends on criterion Y. The fact that Y isn't always true doesn't make X useless.Now, in my opinion, it's frustrating that .NET doesn't have general
SortandBinarySearchmethods for anyIList<T>implementation (e.g., as extension methods). If it did, we could easily sort and search for items within any non-read-only collection providing random access.Then again, you can always write your own (or copy someone else's).
其他人指出，
BinarySearch在排序的List上非常有用。不过，它并不真正属于List，任何具有 C++ STL 经验的人都会立即意识到这一点。随着最近 C# 语言的发展，定义排序列表的概念（例如，
ISortedList: IList ）并定义BinarySearch（等）变得更有意义。 .al.）作为该接口的扩展方法。这是一种更干净、更正交的设计类型。我已经开始将其作为 Nito.Linq 库的一部分进行操作。我预计第一个稳定版本将在几个月内发布。
Others have pointed out that
BinarySearchis quite useful on a sortedList<T>. It doesn't really belong onList<T>, though, as anyone with C++ STL experience would immediately recognize.With recent C# language developments, it makes more sense to define the notion of a sorted list (e.g.,
ISortedList<T> : IList<T>) and defineBinarySearch(et. al.) as extension methods of that interface. This is a cleaner, more orthogonal type of design.I've started doing just that as part of the Nito.Linq library. I expect the first stable release to be in a couple of months.
是的，但是 List 也有 Sort() 方法，因此您可以在 BinarySearch 之前调用它。
yes but List has Sort() method as well so you can call it before BinarySearch.
搜索和排序是算法原语。这对于标准库快速可靠的实现很有帮助。否则，开发人员会浪费时间重新发明轮子。
然而，就 .NET Framework 而言，不幸的是，算法的特定选择恰好使它们没有应有的有用。在某些情况下，它们的行为未定义：
List.BinarySearch 如果 List 包含多个具有相同值的元素，则该方法仅返回出现的一个，并且它会返回可能会返回出现的任何一个，不一定是第一个。List此实现执行不稳定的排序；也就是说，如果两个元素相等，它们的顺序可能不会保留。相反，稳定排序会保留相等元素的顺序。这是一种耻辱，因为有同样快的确定性算法，而且这些算法作为构建块会更有用。值得注意的是，Python、Ruby 和 Go 中的二分查找算法都会找到第一个匹配元素。
Searching and sorting are algorithmic primitives. It's helpful for the standard library to have fast reliable implementations. Otherwise, developers waste time reinventing the wheel.
However, in the case of the .NET Framework, it's unfortunate that the specific choices of algorithms happens to make them less useful than they might be. In some cases, their behaviour is not defined:
List<T>.BinarySearchIf the List contains more than one element with the same value, the method returns only one of the occurrences, and it might return any one of the occurrences, not necessarily the first one.List<T>This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.That's a shame, because there are deterministic algorithms that are just as fast, and these would be much more useful as building blocks. It's noteworthy that the binary search algorithms in Python, Ruby and Go all find the first matching element.
我同意在未排序的列表上调用 BinarySearch 是完全愚蠢的，但如果您知道您的大列表已排序，那就完美了。
我在检查流中的项目是否存在于（或多或少）包含 100,000 个或更多项目的静态列表中时使用过它。
二进制搜索列表比列表查找快几个数量级，这比数据库查找快多个数量级。
我是有道理的，我很高兴它在那里（并不是说如果不是的话，实现它将是火箭科学）。
I agree it's completely dumb to Call BinarySearch on an unsorted list, but it's perfect if you know your large list is sorted.
I've used it when checking if items from a stream exist in a (more or less) static list of 100,000 items or more.
Binary Searching the list is ORDERS of magnitude faster than doing a list.Find, which is many orders of magnitude faster than a database look up.
I makes sense, and I'm glad it there (not that it would be rocket science to implement it if it wasn't).
也许另一点是数组同样可以是未排序的。因此从理论上讲，对数组进行 BinarySearch 也可能是无效的。
然而，与高级语言的所有功能一样，它们需要由有理性并理解数据的人来应用，否则就会失败。当然，可以应用一些交叉检查，并且我们可以有一个表示“IsSorted”的标志，否则它会在二分搜索中失败，但是......
Perhaps another point is that an array could be equally as unsorted. So in theory, having a BinarySearch on an array could be invalid too.
However, as with all features of a higher level language, they need to be applied by someone with reason and understanding of the data, or they will fail. Sure, some cross-checks could be applied, and we could have a flag that said "IsSorted" and it would fail on binary search otherwise, but .....
一些伪代码：
Some pseudo code: