List<T>.BinarySearch是最快的方法吗？

Question

我遇到了在列表中查找项目的编程代码。当我问为什么要使用这个代码时，他们说因为这样可以更快地运行。

这是真的吗？

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;
}

比……更快的方式

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

- PaataPP

---

请阅读此链接：https://en.wikipedia.org/wiki/Binary_search_algorithm - Matthew Watson

二分查找的时间复杂度为O(log n)，而线性查找的时间复杂度为O(n)。然而，二分查找假定集合已经排序，如果没有排序，您需要考虑排序集合所需的时间。 - Matthew

如果按ID查找是一个重要的性能关键操作：考虑使用Dictionary<int, Location>，并使用TryGetValue - 这样它就是O(1)。 - Marc Gravell

@MarcGravell Dictionary<int, Location> 更快，但代价是增加了内存占用（每个项大约多12字节）。 - Theodor Zoulias

二分查找不仅需要集合已经排序，而且元素甚至可以进行比较。并非每种类型都有自然的排序顺序。 - Jon Skeet

Answer 1

这个方法比较快，但只有在以下情况下才适用：

• Location类实现了IComparable接口，并根据Id的值定义了“大于”和“小于”的判断条件
• 列表已经按照Id进行排序

这意味着它不能用于任意列表，也不能根据不属于列表类型的IComparable定义中的其他属性查找值。而使用FirstOrDefault方法更通用，但性能相对较弱。

- D Stanley