何时使用List<T>.BinarySearch？

Question

.NET中的通用List<T>具有BinarySearch()方法。 BinarySearch()是一种高效的搜索大型数据集的算法。我认为我读过，如果全世界的人都在电话簿中列出来，那么二分查找可以在35步内找到任何人。在什么情况下应该在List上使用BinarySearch()，而不是使用带有lambda的标准.Where子句？数据集应该有多大才能从Where切换到BinarySearch？或者Where已经在幕后使用二分搜索了吗？

- user6411982

Answer 1

何时使用 List<T>.BinarySearch？

如您所见，在文档手册中：

搜索整个已排序的 List<T>，使用默认比较器并返回元素的零基索引。

此外，它只能用于匹配给定的元素，而不是谓词，因为通用谓词会破坏顺序约束。

因此，列表必须按照默认比较器或给定比较器进行排序：

public int BinarySearch(T item)                        //default comparator
public int BinarySearch(T item, IComparer<T> comparer) //given comparator

该算法的运行时间为O(log n)，而where子句的运行时间为O(n)。这意味着在实际应用中，它几乎总是优于后者（除非很可能找到的元素位于列表前面）。

那么.Where是否已经在后台使用二进制搜索了？

不，不能这样做。 List<T>并不总是排序的。首先检查列表是否排序，或对列表进行排序将需要计算工作量为O(n)或O(n log n)，成本甚至比线性搜索更高。换句话说，首先检查列表是否排序，然后（如果情况确实如此）执行二进制搜索的成本比执行线性搜索更高。线性搜索可以处理无序列表和谓词，但成本要高得多。

- Willem Van Onsem

Answer 2

在何时应该使用BinarySearch()而不是使用带有lambda的标准Where从而在列表上进行搜索呢？

只要列表相对于您要搜索的值排序，BinarySearch将会（平均而言）比Where提供更好的性能，无论列表的大小如何。

如果列表未排序或其排序方式与您要查找的值不对应（例如，您不能使用二分搜索按名字在电话簿中查找人），则BinarySearch将无法给您正确的结果。

请注意，它只返回一个索引，而Where将会给出所有匹配条件的项，但是如果有重复项，则可以在找到元素的两侧进行搜索（BinarySearch仅提供了一个匹配的索引，而不一定是第一个索引）。

显然，列表越大，使用BinarySearch将获得更多的改进。

Where是否已经在后台使用二分搜索？

否 - 它会按物理顺序遍历列表。

- D Stanley