使用 for 循环的二进制搜索，在列表中搜索单词并进行比较

Question

我正在尝试比较 "alice_list" 和 "dictionary_list" 中的单词，如果在 "dictionary_list" 中找不到单词，则打印它并说它可能拼写错误。我遇到了问题，如果找不到它就不会打印任何东西，也许你们可以帮助我。我将 "alice_list" 附加到大写，因为 "dictionary_list" 全部为大写字母。任何关于为什么它不起作用的帮助将不胜感激，因为我正要把我的头发拉到它上面！

       import re
    # This function takes in a line of text and returns
    # a list of words in the line.

    def split_line(line):
        return re.findall('[A-Za-z]+(?:\'[A-Za-z]+)?', line)
    # --- Read in a file from disk and put it in an array.

    dictionary_list = []
    alice_list = []
    misspelled_words = []

    for line in open("dictionary.txt"):
        line = line.strip()
        dictionary_list.extend(split_line(line))

    for line in open("AliceInWonderLand200.txt"):
        line = line.strip()
        alice_list.extend(split_line(line.upper()))


    def searching(word, wordList):
        first = 0
        last = len(wordList) - 1
        found = False
        while first <= last and not found:
            middle = (first + last)//2
            if wordList[middle] == word:
                found = True
            else:
                if word < wordList[middle]:
                    last = middle - 1
                else:
                    first = middle + 1
        return found


    for word in alice_list:
        searching(word, dictionary_list)

------------ 编辑后的有效代码---------- 如果有人有同样的问题，请更新一些内容，并使用 "for word not in" 仔细检查搜索中输出的内容。

"""-----Binary Search-----"""
# search for word, if the word is searched higher than list length, print
words = alice_list
for word in alice_list:
        first = 0
        last = len(dictionary_list) - 1
        found = False
        while first <= last and not found:
            middle = (first + last) // 2
            if dictionary_list[middle] == word:
                found = True
            else:
                if word < dictionary_list[middle]:
                    last = middle - 1
                else:
                    first = middle + 1
                if word > dictionary_list[last]:
                    print("NEW:", word)

# checking to make sure words match
for word in alice_list:
    if word not in dictionary_list:
        print(word)

Answer 1

你的函数split_line()returns一个列表。然后获取该函数的输出并将其附加到字典列表中，这意味着字典中的每个条目都是一个 list 单词而不是单个单词。快速修复它以使用 extend 而不是 append.

    dictionary_list.extend(split_line(line))

在这里，集合可能比列表更好，那么您就不需要二分查找了。

--编辑--
要打印不在列表中的单词，只需根据您的函数 returns False 过滤列表即可。类似于：

notfound = [word for word in alice_list if not searching(word, dictionary_list)]

Answer 2

这个程序需要使用二分查找吗？ Python 有一个方便的运算符 "in"。给定一个元素作为第一个操作数，list/set/dictionary/tuple 作为第二个操作数，如果该元素在结构中，则 returns 为真，否则为假。

示例：

1 in [1, 2, 3, 4] -> True
"APPLE" in ["HELLO", "WORLD"] -> False

因此，对于您的情况，大部分脚本可以简化为：

for word in alice_list:
    if word not in dictionary_list:
        print(word)

这将打印不在词典列表中的每个单词。

使用 for 循环的二进制搜索，在列表中搜索单词并进行比较

Binary Search using a for loop, searching for words in a list and comparing

python

algorithm

search

binary-search