c# - 什么时候使用 List.BinarySearch？

Question

通用 List<T>在 .NET 中有一个 BinarySearch() 方法。 BinarySearch()是搜索大型数据集的有效算法。我想我读到过，如果世界上的每个人都列在电话簿中，那么二进制搜索可以在 35 步内找到任何人。 BinarySearch() 应该在什么时候用于 List而不是使用标准 .Where带有 lambda 的子句？在从 Where 切换之前，数据集应该有多大？至 BinarySearch ？或者 Where已经在幕后使用了二进制搜索？

Answer 1

When to use List<T>.BinarySearch?

正如您在 documentation manual 中所读到的那样:

Searches the entire sorted List<T> for an element using the default comparer and returns the zero-based index of the element.

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

因此必须对列表进行排序，可以通过默认比较器，也可以通过给定比较器:

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

该算法在 O(log n) 时间内运行，而 where子句在 O(n) 时间内运行，这意味着在实践中它几乎总是优于第二个(除非该元素很可能位于列表的前面)。

Or does .Where already use a binary search behind the scenes?

不，它不能因为。 List<T>并不总是排序。首先检查列表是否已排序，或者对列表进行排序分别需要 O(n) 或 O(n log n) 的计算量，它们是相同的甚至比线性搜索更昂贵。换句话说，首先检查列表是否已排序，然后 - 如果是这种情况 - 执行二进制搜索将比执行线性搜索更昂贵。线性搜索可以处理无序列表和谓词，但成本要高得多。