搜索记录没有扫描所有的记录

我有一个记录（结构）的名单如下：搜索记录没有扫描所有的记录

struct Rec 
{ 
    int WordID; 
    int NextID; 
    int PrevID; 
} 

List<Rec>= New List<Rec>(){...};

我需要一种方法来查找列表“REC”类型的值不搜索所有记录，如二进制搜索。我希望它的时间复杂度小于O（n）

2011-11-05 Amin

你能给我们更多的细节吗？你需要进行什么样的搜索？你必须通过WordID搜索？ –

我需要搜索所有项目（WordID，NextID和PrevID）。我使用二进制搜索对单个项目记录执行了二进制搜索，现在我想用三个项目搜索它。 – Amin

正如我所说，如果你有一个散列表，搜索速度会非常快。 –

在列表中搜索项目的最佳方式当然不是列表，而是具有散列表。

如果您有字典而不是列表（或字典和列表），则可以在平均值\摊销O（1）中执行精确值搜索。

您也可以使用二进制搜索，但只有当列表排序后，才有方法List<T>.BinarySearch，并且搜索结果为O（log n）。

用n个项目对列表排序为O（n log n）。将n个项目插入散列表中，取而代之的是O（n），插入项目的平均值为O（1）。这意味着创建散列表（或保持散列表与列表同步）将比排序列表快。然而，考虑到散列表会消耗更多的内存，因为它们必须在内部保留一个存储桶阵列。

2011-11-05 09:37:20

我使用了BinarySearch，比如'Rec.BinarySearch（new rec（10，20，30））'，但是我收到了这个错误：_Failed比较了array_中的两个元素 – Amin

这意味着你使用了一个错误的比较算法，在您的结构中实现IComparable 并编写正确的CompareTo实现。 –

对于散列表，你应该覆写Equals和GetHashCode方法。 –

您可以使用二进制搜索，提供您的列表排序。

2011-11-05 09:33:51

回答