LINQ中的Where子句内部采用二分查找还是线性查找

核心结论：使用Where这类通用LINQ方法筛选List<T>元素时，无论集合存储的是整数、字符串还是自定义对象，内部默认都执行线性查找，不会自动触发二分查找。

• 二分查找的前置依赖非常严格：要求待查找集合必须按照查找对应的比较规则提前完成排序，查找过程需要依赖明确的顺序比较逻辑才能折半缩小范围。标准LINQ to Objects的Where、带谓词的First/FirstOrDefault、带谓词的Count这类通用筛选方法，既不会校验当前集合是否有序，也不会感知你写的筛选条件和集合排序规则是否匹配，根本不满足自动执行二分查找的前提。
• 这类通用筛选方法的内部实现逻辑是从头至尾逐一遍历集合中的每个元素，用你传入的lambda条件逐个做匹配判断，时间复杂度为O(n)，属于典型的线性扫描。

只有显式调用二分查找相关API时才会执行二分逻辑，常见场景包括：

1. 手动调用List<T>实例自带的BinarySearch()方法，调用前必须自行保证列表已经按照对应比较规则完成排序，否则查找结果不可靠；
2. 针对已经排序的IOrderedEnumerable序列，使用专门为有序序列设计的二分查找扩展方法（这类方法不属于原生LINQ标准API，多为自定义扩展或第三方库提供）。

你给出的自定义类和查询示例的执行逻辑如下：

public class Person
{
    public string Name { get; set; }
    public string Address { get; set; }
}

List<Person> persons = new List<Person>();
// 以下查询会线性遍历persons列表的每一个元素，逐个判断Name属性是否等于"kushal"，不会自动做二分查找
persons.Where(x => x.Name == "kushal");

补充常见误区：不要误以为List<T>作为强类型集合自带字段索引，它的底层实现是动态数组，没有针对元素属性建立任何额外的查找索引，只要你不手动调用二分查找相关API、不使用专门为有序集合设计的优化方法，所有带自定义条件的筛选都是线性遍历。

内容的提问来源于stack exchange，提问作者KushalSeth