当前位置: 动力学知识库 > 问答 > 编程问答 >

python - Binary search for a string in a list of strings

问题描述:

I have a list of permutations of a string, and a list full of words from a lexicon. I want to for each permutation find out if it's in the list of words. I tried a while loop and just brute-forced through and that gave me a bunch of words from the wordlist. But when I tried this binary search:

def binärSökning(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

I got nothing in return, just an empty list (Just false, if it returns true it adds the word to another list). Can anyone please tell me why it's not returning true when it hits a good word?

Edit:

What's calling the function is just a for-loop:

foundWords = set()

for word in listOfWords:

if binärSökning(word, NewWordList):

foundWords.add(word)

return foundWords

Where the NewWordList is the a narrower list of possible words it could be, nothing wrong with it, since it worked when I tried brute force.

What I would like as a result is when ever the searching function returns true, the for-loop adds that word to a set that is then presented to the user once the program finishes.

网友答案:

If you have a list of words, it is as simple as making a single if statement as follows:

def bomrSkning(word, wordList):
    found = False
    if word in wordList:
        found = True
    return found
网友答案:

It was working fine for me. The following was my code:

def binrSkning(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

The following was my output

>>> binrSkning('hi', ['hello', 'hi', 'how'])
True
>>> binrSkning('tim', ['hello', 'hi', 'how'])
False

The following worked fine for me:

>>> NewWordList = ['hello', 'hi', 'how']
>>> listOfWords = ['hi', 'how', 'bye']
>>> foundWords = set()
>>> for word in listOfWords:
        if binrSkning(word, NewWordList):
            foundWords.add(word)

>>> foundWords
set(['how', 'hi'])
分享给朋友:
您可能感兴趣的文章:
随机阅读: