Бинарный поиск строки в списке строк

Question

У меня есть список перестановок строки и список, полный слов из лексики. Я хочу, чтобы для каждой перестановки выяснялось, находится ли она в списке слов. Я пробовал цикл while и просто грубо-принудительный, и это дало мне кучу слов из списка слов. Но когда я попробовал этот бинарный поиск:

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 

я не получил ничего взамен, просто пустой список (просто ложь, если она возвращает истину, он добавляет слово в другой список). Может кто-нибудь, пожалуйста, скажите мне, почему это не возвращает истину, когда она попадает в хорошее слово?

Edit: Что вызов функции просто для петли:

foundWords = set() 

for word in listOfWords: 
    if binärSökning(word, NewWordList): 
     foundWords.add(word) 

return foundWords 

Если NewWordList является более узкий список возможных слов, это может быть, ничего плохого с ним, так как он работал, когда я попробовал грубую силу.

Что бы я хотел в результате, когда функция поиска возвращает true, цикл for добавляет это слово к набору, которое затем представляется пользователю после завершения программы.

Answer 1

Это работало отлично для меня. Ниже мой код:

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 

Ниже мой выход

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

Следующая обработанное отлично для меня:

>>> 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']) 

Answer 2

Если у вас есть список слов, это как прост как один из следующих утверждений:

def bomrSkning(word, wordList): 
    found = False 
    if word in wordList: 
     found = True 
    return found