# Jared Wasserman
# 5/19/2013
# Python translation of Arup's Binary Search example for BHCSI

from random import randrange

class binsearch2: 
    
    # Constants for our program.
    numvals = 20
    maxval = 100000
    printflag = True
    
    @staticmethod
    def main():
        # Create my_list.
        mymy_list = binsearch2.makeList(binsearch2.numvals, binsearch2.maxval)
        if (binsearch2.printflag): 
            binsearch2.printList(mymy_list)
        
        # Check if the my_list is already sorted or not.
        if (not(binsearch2.isSorted(mymy_list))):
            print("not sorted.")
        
        # Now sort.
        mymy_list.sort()
        if (binsearch2.printflag):
            binsearch2.printList(mymy_list)
        
        # Now it should be sorted.
        if (binsearch2.isSorted(mymy_list)):
            print("is sorted.")
        
        # Get the value to search for.
        val = int(input("For which value do you want to search?\n"))
        
        # Search for it and print out the results.
        if (binsearch2.search(mymy_list, val)):
            print(str(val) + " is in the array.")
        else:
            print(str(val) + " is NOT in the array.") 
    
    # Returns true iff my_list is in sorted order.
    @staticmethod
    def isSorted(my_list): 
        # Look to see if any adjacent pairs are out of order.
        for i in range(len(my_list) - 1):
            if (my_list[i + 1] < my_list[i]):
                return False
                
        # If not, it's sorted.
        return True
    
    # Runs a binary search for value in my_list. Assumes my_list is sorted from
    # smallest to largest.
    @staticmethod
    def search(my_list, value):
        # Set bounds for binary search.
        low = 0
        high = len(my_list) - 1
        
        # Search until there's no search space.
        while (low <= high):
            
            # Look in the middle.
            mid = int((low + high) / 2)
            
            # Reduce the search space as necessary.
            if (value > my_list[mid]):
                low = mid + 1
            elif (value < my_list[mid]):
                high = mid - 1
            else:
                return True
        
        # If we get here, the value isn't in the my_list.
        return False
    
    # Returns an my_list with size elements in the range [1,max].
    @staticmethod
    def makeList(size, maxvalue):
        
        my_list = [None] * size
        
        for i in range(len(my_list)):
            my_list[i] = randrange(0, maxvalue) + 1
            
        return my_list
    
    # Prints the contents of my_list.
    @staticmethod
    def printList(my_list): 
        for i in range(len(my_list)):
            print(str(my_list[i]) + " ")
        print()

# runs main module on startup
if __name__ == "__main__":
    binsearch2.main()