# NAMES REMOVED
#CSC323: Software Design
#February 3, 2010
#Assignment 2: Python Basics: binary search

import random

def rand_list (num_elements, range_min, range_max):
        """Make a list of sorted random numbers, with the integer num_elements as the number of elements between the integer            range of range_min and range_max."""
        randomnums = []
        for i in range(0, num_elements):
                randomnums.append(random.randint (range_min, range_max))
        randomnums.sort()
        return randomnums

def binary_search (i,vals):
        """binary_search: takes integer i to search for in vals, a list of sorted integers.  Returns an index of i if it appears        in vals; otherwise, it returns -1."""
        return binary_search_kernel(i, vals, 0, len(vals) - 1)

def binary_search_kernel (key, array, low, high):
        """Searches an array from array[low] to array[high] for a key"""
        if low > high:  
                return -1
        mid = (high + low) // 2
        if key == array[mid]:
                return mid
        elif key < array[mid]:
                #The key is smaller than mid, search lower half of array
                return binary_search_kernel (key, array, low, mid - 1)
        else:
                #The key is greater than mid, search upper half of array
                return binary_search_kernel (key, array, mid + 1, high)

#Test cases: We used the following test cases to check that binary_search is correctly 
#implemented.
def tester (array):
        """Test procedure. Prints nice text saying if things were found"""
        print(array)
        for x in range(min(array)-5,max(array)+5):
                result = binary_search (x,array)
                if result == -1:
                        print(x, "was not found.")
                else:
                        print (x, "was found at index:", result)