"""
 binsearch.py

 A binary search example.

 Note that even with a quarter of a million (ordered) words to 
 look through, the search only steps through fifty python lines.

 Jim Mahoney | cs.marlboro.college | Jan 2019 | MIT License
"""

def get_words(filename="./words.txt"):
   """ return a list of strings, in alpha order 
       >>> words = get_words()
       >>> len(words)
       235886
       >>> words[:5]
       ['A', 'a', 'aa', 'aal', 'aalii']
       >>> words[-5:]
       ['zythem', 'Zythia', 'zythum', 'Zyzomys', 'Zyzzogeton']
   """
   # ./words.txt is /usr/share/dict/words file# on my macOS 10.14.3 (Mojave).
   # It's (a) pretty big and (b) already in order.
   # (Oh, and Zyzzogeton? See https://en.wikipedia.org/wiki/Zyzzogeton .)
   return list(map(lambda s: s.strip(), open(filename).readlines()))

def search(word, words):
    """ Given an ordered list words, return (i, steps) 
        where that words[i] == word and steps is the number of steps 
        taken in the search. Return (False, steps) when the word isn't found.
        >>> search('cat', ['ant', 'beetle', 'cat', 'dog', 'zebra'])
        (2, 5)
        >>> search('frog', ['ant', 'beetle', 'cat', 'dog', 'zebra'])
        (False, 9)
        >>> search('medical', get_words())
        (112883, 50)
        >>> search('mydical', get_words())
        (False, 54)
    """
    steps = 0
    lo_index = 0
    steps += 1
    hi_index = len(words)-1
    steps += 1
    while lo_index < hi_index:
        steps += 1
        i = (lo_index + hi_index) // 2
        steps += 1
        if words[i] == word:
            steps += 1
            return (i, steps)
        elif word < words[i]:
            steps += 1
            hi_index = i - 1
        elif word > words[i]:
            steps += 1
            lo_index = i + 1
    steps += 1
    return (False, steps)

if __name__ == '__main__':
    import doctest
    doctest.testmod()