Binary search for a string in a list of strings
<p>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:</p>

<pre><code>def binÃ¤rSÃ¶kning(word, wordList):
    first = 0
    last = len(wordList) - 1
    found = False
    while first &lt;= last and not found:
        middle = (first + last)//2
        if wordList[middle] == word:
            found = True
        else:
            if word &lt; wordList[middle]:
                last = middle - 1
            else:
                first = middle + 1
    return found
</code></pre>

<p>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?</p>

<p>Edit:
What's calling the function is just a for-loop:</p>

<pre><code>foundWords = set()

for word in listOfWords:
    if binÃ¤rSÃ¶kning(word, NewWordList):
        foundWords.add(word)

return foundWords
</code></pre>

<p>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.</p>

<p>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.</p>

<p>It was working fine for me. The following was my code:</p>

<pre><code>def binrSkning(word, wordList):
    first = 0
    last = len(wordList) - 1
    found = False
    while first &lt;= last and not found:
        middle = (first + last)//2
        if wordList[middle] == word:
            found = True
        else:
            if word &lt; wordList[middle]:
                last = middle - 1
            else:
                first = middle + 1
    return found
</code></pre>

<p>The following was my output</p>

<pre><code>&gt;&gt;&gt; binrSkning('hi', ['hello', 'hi', 'how'])
True
&gt;&gt;&gt; binrSkning('tim', ['hello', 'hi', 'how'])
False
</code></pre>

<p>The following worked fine for me:</p>

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

&gt;&gt;&gt; foundWords
set(['how', 'hi'])
</code></pre>

python python-3.x binary-search