'''
   20211024
   
   Robin Dawes
   
   Binary Search
'''

# Binary search is a fundamental algorithm that you will encounter over
# and over.  Whenever you learn a new programming language, a good
# exercise is to write a binary search function in the new language.

# The basic idea is that if we are searching a sorted list (or array) of numbers
# to find a particular value, we can start by looking at the value in the middle
# of the list.  If it is the one we are looking for, hurray, we can stop.  But if it
# is too big, then all the numbers after it in the list are also too big (because the
# list is sorted) so we can continue the search in just the first half of the list.  
# Similarly, if the value we look at in the middle is too small, we can continue 
# the search in just the second half of the list.  In this way we repeatedly cut 
# the size of the search area in half until we either find the search target or 
# conclude that it is not there.

# I'm calling this binary_search_v1 because it's just the first version, and it's not 
# the best version.  This is not the version to use!
def binary_search_v1(a_list, target):
   ''' if target is in a_list, returns the index of the location
      if taget is not in a_list, returns -1
      reduces the list by slicing to just the positions that haven't been eliminated
   '''
   if len(a_list) == 0:
      return -1
   else:
      mid = (len(a_list) - 1) // 2
      if a_list[mid] == target:
         return mid
      elif a_list[mid] > target:
         return binary_search_v1(a_list[:mid], target)
      else:
         return binary_search_v1(a_list[mid+1:], target)

# The version of binary_search just given always finds the right answer, but it's 
# very inefficient!  The problem is that making a slice of the list every time
# forces it to do a lot of copying. We can avoid making copies of the list by passing two more
# parameters to the recursive function which tell it which part of the list we
# are currently working on.  

# In the earlier posted demo code called "Recursion Examples" I presented the
# rationale for using what we call a "helper function" to set up and start the 
# efficient recursive function.  Please refer back to the notes in that demo.

# The purpose of the helper function is to serve as the interface between
# the user and the recursive function.  The user supplies the list and the value
# to be searched for.  The helper function calls the recursive function with 
# appropriate parameters.

def binary_search(a_list, target):
   ''' assumes a_list is in sorted order 
       if target is in a_list, returns its position
       if target is not in a_list, returns -1
   '''
   return bin_search_rec(a_list, target, 0, len(a_list)-1)
   

def bin_search_rec(the_list, target, first, last):
   '''
      recursively searches the_list for target, looking at the values from 
      the_list[first] up to the_list[last], inclusive.
   '''
   if first > last:            # Our recursive function MUST have a base case
                                    # In this case, we end the recursion when the range
                                    # of possible locations for x shrinks to 0
      return -1
   else:
      mid = (first + last) // 2                   # find the middle position
      if the_list[mid] == target:             # if target is found, return this position   
         return mid
      elif the_list[mid] > target:             # check to see if we go to the left ...
         return bin_search_rec(the_list, target, first, mid - 1)
      else:                                               # ... or to the right
         return bin_search_rec(the_list, target, mid +1, last)
         
         
# testing the binary search function         
         
import random          
         
my_list =  random.sample(range(1000), 15)    # choose 15 random numbers
                                                                            # from this range

print("\noriginal list", my_list)            # the values are in random order
target = my_list[0]                             # pick the first number chosen to be the one
                                                           # to be searched for
my_list.sort()
print("\nsorted list", my_list)               # who knows where that target value is now?
print("\nsearching for", target)
print("\n", target, "is now in position", binary_search(my_list, target))
                                                            # binary_search knows, that's who!