搜索記錄沒有掃描所有的記錄

我有一個記錄（結構）的名單如下：搜索記錄沒有掃描所有的記錄

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

回答