c# - 如何快速搜索单词或数字 c#

Question

我确定存在这样的东西，但我不知道它会被称为什么(或如何找到更多信息)。如果我有一个按字母顺序排序的单词列表，并且我正在检查以查看if 和where 单词“test”在该列表中，这没有意义从头开始，但从 T 开始，对吗？当然，数字也是如此。有没有办法实现这样的东西并定制搜索的开始？还是 hash sets 和 Contain 之类的方法自己已经做到了？

编辑:

例如，如果我有一个像 {1,2,3,5,7,8,9,23..} 这样的整数列表，是否有自动排序的方法，以便当我检查列表元素“9”，它不是从头开始......？

抱歉，这是一个简单的例子，但我确实打算在一个可能包含数千个元素的列表中搜索数千次

编辑 2:

从回复中，我了解了二进制搜索，但由于它显然是从列表的中间开始的，是否可以手动实现一些东西，例如，将单词列表分成 26 个箱子这样当你搜索一个特定的词时，它可以立即开始在最佳位置搜索(或者可能是 52 个箱子，如果每个箱子开始变得过多......)

Answer 1

当您说您有一个排序列表并且想要搜索它时，我 立即想到的算法是二分查找。还好List<T> already has that implemented .

该链接上的示例实际上看起来完全符合您的要求(它也在处理在已排序单词列表中查找单词)。

本质上，你想要这样的东西:

List<string> words = ...;

words.Sort(); // or not depending on the source

var index = words.BinarySearch("word");

if(index > -1)
{
    // word was found, and its index is stored in index
}
else // you may or may not want this part
{    // this will insert the word into the list, so that you don't have to re-sort it.
    words.Insert(~index, "word");
}

当然，这也适用于 int秒。只需替换 List<string>与 List<int>和你的 BinarySearch与 int 争论.

大多数Contains -type 函数简单地循环遍历集合，直到找到您要查找的项目。这很好用，因为您不必先对集合进行排序，但是当您开始对集合进行排序时就不太好了。所以在大多数情况下，如果您经常搜索同一个列表，请对其进行排序并 BinarySearch它，但是如果你修改列表很多并且只搜索一次或两次，那么常规的 IndexOf或 Contains可能是您最好的选择。

---

如果您想按首字母对单词进行分组，我可能会使用 Dictionary<char, List<string>>存储它们。我选择了List出于可变性的目的在数组上进行调用，因此请自行调用——还有 Array.BinarySearch如果您选择使用数组。您可以使用专有的树模型，但这可能会或可能不会矫枉过正。要执行由第一个字符键入的字典，您需要这样的东西:

Dictionary<char, List<string>> GetDict(IEnumerable<string> args)
{
    return args.GroupBy(c => c[0]).ToDictionary(c => c.Key, c => c.OrderBy(x => x).ToList());
}

然后您就可以像以前一样非常简单地使用它。唯一的变化在于获取您的列表。

Dictionary<char, List<string>> wordsByKey = GetDict(words);
List<string> keyed;
string word = "word";

if (wordsByKey.TryGetValue(word[0], out keyed))
{
    // same as before
}
else
{
    wordsByKey.Add(word[0], new List<string>() { word }); // or not, again
                                                          // depending on whether you
                                                          // want the list to update.
}