通过修改二进制搜索算法来改进二进制搜索算法,以便在搜索大量单词(单词列表)时更快地工作

Question

我想从排序单词列表中搜索特定单词.我的单词列表包含100,000个单词.为了提高二进制搜索算法的性能,我想稍微修改一下.例如,如果我想搜索单词"apple"而不是在整个单词列表中应用二进制搜索算法.我将它仅应用于以字母'a'开头的单词.如果我在数组或向量中加载单词列表,我知道我会从索引0开始搜索.问题是我不知道对于以字母'a'开头的单词的最后一个索引是什么.关于如何知道最后一个索引的任何想法？

Answer 1

我建议你实现TRIE而不是实现二进制搜索算法.例如:每个字母都是TRIE的节点.构建TRIE的时间复杂度为O(W*L).W是字数.L是单词的平均长度.当您从TRIE中找到单词时,需要O(L).