在列表中搜索一条记录，而不扫描所有记录
本文关键字：记录 扫描 搜索 一条 列表 | 更新日期: 2023-09-27 18:13:31
我有一个像这样的记录(结构)列表:
struct Rec
{
int WordID;
int NextID;
int PrevID;
}
List<Rec>= New List<Rec>(){...};
我需要一种方法来找到列表中"Rec"类型的值，而无需搜索所有记录，如二进制搜索。我希望它的时间复杂度小于O(n)
在列表中搜索项的最好方法当然不是列表，而是哈希表。
如果你有一个字典而不是一个列表(或者一个字典和一个列表)，你可以在平均'平摊O(1)中执行精确值搜索。
你也可以使用二分查找，但只有当列表被排序时，才有方法List<T>.BinarySearch和搜索为O(log n)。
排序n个元素的列表耗时O(n log n)。在哈希表中插入n个元素的平均时间是O(n)，插入一个元素的平均时间是O(1)。这意味着创建哈希表(或保持哈希表与列表同步)将比排序列表更快。然而，考虑到哈希表消耗更多的内存，因为它们必须在内部保持一个桶数组。
您可以使用二进制搜索，只要您的列表已排序。