# CSC323 Assignment 2:

# NAMES REMOVED

# Import the math library
import math

# Define a class to carry out the search
class searcher ():
    def __init__ (self):
        pass

    # wrapper method for the recursive implementation
    # parameters are the int to be searched for, i,
    # and the set of values to search, vals
    # Preconditions: vals is sorted in increasing order
    # Returns: -1 if i is not in vals, otherwise the index is returned
    def binary_search (self, i, vals):

        return self.bsinner(i, 0, len(vals), vals)

    # recursive implementation

    # additional parameters are markers so the procedure knows what part of the array
    # it is working on
    def bsinner (self, i, a, b, vals):

        # if a = b, the element is not in the list
        if a == b:
            return -1

        # check to see if the middle element is i, if so return the index
        if vals[self.middle(a,b)] == i:
            return self.middle(a,b)

        # check to see if the element is in the top half, or the bottom half
        elif vals[self.middle(a,b)] >= i:
            # if it is in the bottom half, recurse on bottom
            return self.bsinner(i,a,self.middle(a,b),vals)
        else:
            # if it is in the top half, recurse on top
            return self.bsinner(i,self.middle(a,b)+1,b,vals)


    # a helper method to find the middle
    # Parameters: two integers
    # Returns: The floor of the average of the two integers.
    def middle (self, a, b):
        return math.floor((a+b)/2 )


# Testing!

if __name__=="__main__":

    # create a searcher
    s = searcher()
    
    # boolean that stores true, will change to false if at any point a test fails
    test = True
    
    # build an even-sized array from 1-10
    vals = list(range(1,10))

    # runs the bsearch method on each value in the list vals
    # the expected position of each n in the list should be n-1
    # if at any point the method returns an incorrect result, test is set to false
    for i in range (0,9):
        if not s.binary_search(i, vals) == i-1:
            test = False

    # repeates the above test, but with an array of odd size
    vals2 = list(range(1, 9))
    for i in range(1,9):
        if not s.binary_search(i, vals) == i-1:
            test = False

    # removes the integer 6 from the list vals    
    vals.pop(5)

    # bsearch with i = 6
    # if bsearch returns an index instead of -1, set test to False
    if not s.binary_search(6,vals) == -1:
        test = False

    # print the results of the testing
    if test == True:
        print ("The tests were successful.");
    else:
        print ("The tests were not successful.")