时间戳

首页 > 解决方案 > 使用 for 循环进行二分搜索，在列表中搜索单词并进行比较

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

问题描述

我正在尝试将“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)

标签： pythonalgorithmsearchbinary-search

解决方案

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

    dictionary_list.extend(split_line(line))

在这里，集合可能比列表更好，那么您就不需要二进制搜索。

--EDIT--
要打印不在列表中的单词，只需根据您的函数是否返回来过滤列表False。就像是：

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

推荐阅读