text: # -*- coding: utf-8 -*-
  """
  Created on Wed Apr 10 21:36:27 2019
  
  @author: Falble
  """
  
  import bisect
  
  
  def make_word_list():
      """Reads lines from a file and builds a list using append.
      returns: list of strings
      """
      word_list = []
      fin = open('words.txt')
      for line in fin:
          word = line.strip()
          word_list.append(word)
      return word_list
  
  
  def in_bisect(word_list, word):
      """Checks whether a word is in a list using bisection search.
      Precondition: the words in the list are sorted
      word_list: list of strings
      word: string
      returns: True if the word is in the list; False otherwise
      """
      if len(word_list) == 0:
          return False
  
      i = len(word_list) // 2
      if word_list[i] == word:
          return True
  
      if word_list[i] > word:
          # search the first half
          return in_bisect(word_list[:i], word)
      else:
          # search the second half
          return in_bisect(word_list[i+1:], word)
  
  
  def in_bisect_cheat(word_list, word):
      """Checks whether a word is in a list using bisection search.
      Precondition: the words in the list are sorted
      word_list: list of strings
      word: string
      """
      i = bisect.bisect_left(word_list, word)
      if i == len(word_list):
          return False
  
      return word_list[i] == word
  
  
  if __name__ == '__main__':
      word_list = make_word_list()
      
      for word in ['aa', 'alien', 'allen', 'zymurgy']:
          print(word, 'in list', in_bisect(word_list, word))
  
      for word in ['aa', 'alien', 'allen', 'zymurgy']:
          print(word, 'in list', in_bisect_cheat(word_list, word))
  