Given a list of n integers, write a function to determine if any two sum to k

Three possible solutions:

1. Naive. Compering all pairs of number. 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. Sorting and finding element with Binary Search. 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. Using Hash set. 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