Dada uma lista de n inteiros, escreva uma função para determinar se quaisquer dois somam k

Três soluções possíveis:

1. Ingênuo. Compering todos os pares de números. Perf O (n ^ 2) Mem O (1)

   def find_pair_sum(lst, k):
       if lst is None:
           return
       for i in xrange(0, len(lst)):
           for j in xrange(0, len(lst)):
               if lst[i] + lst[j] == k:
                   yield lst[i], lst[j]
   
   for p in find_pair_sum([1,2,3,4,9,5], 6):
       print p

2. Classificando e encontrando elemento com Pesquisa Binária. Perf O (nlgn) Mem O (1)

   def _binary_search_rec(lst, start, end, elem):   
       if start <= end:
           mid = (end - start) / 2 + start
           if lst[mid] == elem: 
               return True
           elif lst[mid] < elem:
               return _binary_search_rec(lst, mid + 1, end, elem)
           else:
               return _binary_search_rec(lst, start, mid - 1, elem)
   
   def binary_search(lst, elem):
       if lst is None:
           return False
       return _binary_search_rec(lst, 0, len(lst) - 1, elem)
   
   def find_pair_sum(lst, k):
       if lst is None:
           return 
       lst.sort()
       for elem in lst:
           if binary_search(lst, k - elem):
               yield elem, k - elem
   
   for p in find_pair_sum([1,2,3,4,9,5], 6):
       print p

3. Usando o conjunto Hash. Perf O (n) Mem O (n)

   def find_pair_sum(lst, k):
       if lst is None:
           return 
       s = set(lst)
       for elem in s:
           if k - elem in s:
               yield elem, k - elem
   
   for p in find_pair_sum([1,2,3,4,9,5], 6):
       print p