'''binary_search.py

   Jed Yang, 2016-10-26

   Given: - item needle (think an integer)
          - list haystack (think list of integers) of length N.
   Problem 1.  Return True if needle is in haystack (False if not found).
   Problem 2.  Return index of occurrence (or -1 if not found).

   linear_search() loops through haystack in a linear fashion and returns the
   index of the first occurrence of needle.  If needle is not found, -1 is
   returned.  The "(worst-case) time complexity" is linear, since there may be
   N comparisons.  We say that it is O(N) "big Oh of N".

   Binary Search assumes that haystack is sorted.  In the worst case, it makes
   roughly log N comparisons.  So its time complexity is logarithmic, which is
   substantially faster than linear when N is very big.  We say that it is
   O(log N) "big Oh of log N".

   1. Examine the code of linear_search and binary_search_recursive below and
      play with them until you feel confident you understand what they are doing.

   Note binary_search_recursive() below only returns True/False depending on
   whether needle is in haystack, as opposed to returning the index of needle
   in haystack.
   
   2. Enhance the code so it returns the index (and -1 if not found).  If
      needle occurs multiple times in haystack, you can return the index of ANY
      such occurrence (it does NOT need to be the first one).
      Hint: Use binary_search_iterative as a guide.
'''

def linear_search(needle, haystack):
   '''Returns the index of the first occurrence of needle in haystack.
      If not found, return -1.
   '''
   for i in range(len(haystack)):
      if haystack[i] == needle:
         return i
   return -1

print(linear_search(5, [1, 3, 5, 7]))
print(linear_search(4, [1, 3, 5, 7]))


def binary_search_recursive(needle, haystack):
   '''Searches for needle in a SORTED haystack.  Returns True or False.'''
#   print('binary_search_recursive({0}, {1})'.format(needle, haystack))
   if len(haystack) == 0:
      return False

   middle = len(haystack) // 2
#   print('haystack[{0}] = {1}'.format(middle, haystack[middle]))

   if needle == haystack[middle]:
      return True
   elif needle < haystack[middle]:
      return binary_search_recursive(needle, haystack[:middle])
   else:
      return binary_search_recursive(needle, haystack[middle+1:])

print(binary_search_recursive(23, [1, 2, 4, 8, 16,     32, 64, 128, 256, 512, 1024, 2048]))
print(binary_search_recursive(23, [1, 2, 4, 8, 16, 23, 32, 64, 128, 256, 512, 1024, 2048]))

# Extra Time:
#  - Write linear_search() in a recursive way without using loops.
#  - Make binary_search_recursive() return index of first occurrence.
#  - Write sort_search() that sorts its haystack first and then call
#     binary_search.

def binary_search_iterative(needle, haystack):
   '''Performs binary search iteratively to find the index of needle in
      haystack.  Returns -1 if needle is not found.  Assumes haystack is
      sorted.
   '''
   low = 0
   high = len(haystack) - 1
   while low <= high:
      middle = (low + high) // 2
      print('haystack[{0}] = {1}; low = {2}, high = {3}'.format(middle, haystack[middle], low, high))
      if needle == haystack[middle]:
         return middle
      elif needle < haystack[middle]:
         high = middle - 1
      else:
         low = middle + 1
   return -1