List<T>.BinarySearch是否为最快的List查找方式？对比两种实现

项目里遇到一段用BinarySearch在List<Location>中查找记录的代码，询问实现原因时，对方称这种方式运行速度更快。想确认这个说法是否属实？

两种实现对比 #

BinarySearch实现 #

public static Location GetRecordById(this List<Location> records, int? id)
{
    if (id == null) return null;
    int position = records.BinarySearch(new() { Id = (int)id });
    return position >= 0 ? records[position] : null;
}

FirstOrDefault实现 #

public static Location GetRecordById(this List<Location> records, int? id)
{
    if (id == null) return null;
    return records.FirstOrDefault(w => w.Id == id);
}

结论：说法有前提，并非绝对 #

1. 必须满足的核心前提
   要让BinarySearch正确且高效工作，List<Location>必须是按Id字段排序好的，同时Location类必须正确实现IComparable<Location>接口（或者调用BinarySearch时传入匹配的比较器）——二分查找完全依赖有序的元素顺序和正确的比较逻辑，否则会返回错误位置，甚至找不到正确记录。

2. 性能差异场景

   • 当列表有序且数据量较大时：BinarySearch的时间复杂度是O(log n)，而FirstOrDefault是O(n)，此时BinarySearch的查找速度确实远快于后者，数据量越大，性能差距越明显。
   • 当列表无序时：BinarySearch无法正确工作，强行使用会导致查找结果错误。这种情况下要么用FirstOrDefault，要么先对列表排序再用二分查找——但排序本身的时间复杂度是O(n log n)，如果只执行一次查找，排序+二分的总耗时反而会比直接遍历的FirstOrDefault更高。

3. 额外细节提醒
   示例中BinarySearch用了仅初始化Id的匿名Location对象，需要确保类的比较逻辑仅依赖Id字段，否则会出现比较逻辑不匹配的问题。

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