Binary Searches

from random import randint

def generateOrderedList(x):
    elements = list(range(1,x))
    return elements

def generateRandomList(numberOfElements):
    #create list of random numbers
    elements = []
    for i in range(0,numberOfElements):
        value = randint(1,40)
        elements.append(value)
    return elements

def getItem():
    return input('Enter Item to search for: ')

def binarySearch(elements,searchTerm):
    lower = 0
    upper = len(elements)
    while lower <= upper:
        middle = calculateMiddle(lower,upper)
        #print(lower,middle,upper,elements[middle])
        if elements[middle] > searchTerm:
            upper = middle -1
            #print(elements[lower:upper])
        elif elements[middle] < searchTerm:
            lower = middle + 1
            #print(elements[lower:upper])
        else:
            return middle
    return -1



def binarySearchSame(elements,element,direction):
    lower = 0
    upper = len(elements) - 1
    while lower <= upper:
        middle = calculateMiddle(lower,upper)
        #print(lower,middle,upper,elements[middle])
        if elements[middle] > element:
            upper = middle -1
            #print(elements[lower:upper+1])
        elif elements[middle] < element:
            lower = middle + 1
            #print(elements[lower:upper+1])
        else:
            same = True
            prevMiddle = middle
            while same and middle >= 0 and middle <= len(elements):
                if elements[middle] == element:
                    prevMiddle = middle
                    middle = middle + direction
                else:
                    same = False
            return prevMiddle
    return -1


def binarySearchClosest(elements,searchTerm):
    #search for the closet element in list that matchest the search term
    lower = 0
    upper = len(elements) - 1
    lastLower = lower
    lastUpper = upper
    found = False
    loc = 0
    while lower <= upper:
        #print(elements[lower:upper+1])
        middle = calculateMiddle(lower,upper)
        #print(lower,middle,upper,elements[middle])
        #if the middle element is higher than the search term then return the second half of the list else the first half
        if elements[middle] > searchTerm:
            lastUpper = upper
            upper = middle -1
            #print(elements[lower:upper+1])
        elif elements[middle] < searchTerm:
            lastLower = lower
            lower = middle + 1
            #print(elements[lower:upper+1])
        else:
            return (searchTerm,middle)
    #iterate through list between lastLower and lastUpper
    #this next line is only called if the search term is not found
    #the sublist is the list prior to the last list division
    return checkSublist(lastLower,lastUpper,elements,searchTerm)

def checkSublist(lastLower,lastUpper,elements,searchTerm):
    #this is called if the search term is not found
    #loop through all elements and find the item that is closest to the search term
    diff = -1
    closest = -1
    ndiff = 0
    loc = lastLower
    locClosest = 0
    #print(lastLower,lastUpper)
    for item in elements[lastLower:lastUpper+1]:
        ndiff = calculateDifference(searchTerm,item)
        #print(item,item,searchTerm,ndiff)
        if diff == -1 or ndiff < diff:
            diff = ndiff
            closest = item
            locClosest = loc
        loc += 1
    return closest, locClosest

def calculateDifference(element,currentTerm):
    return abs(element - currentTerm)

def calculateMiddle(lower,upper):
    #calculate the middle value between the upper and lower limits of the current sublist
    return int((upper + lower) / 2)

def searchResult(element,closest, location):
    if closest  == '':
        if location == -1:
            print(str(element) + ' is not in the list')
        else:
            print(str(element) + ' was found as index ' + str(location))
    else:
        print('The closest element was {} and was found at index {}'.format(closest,location))





elements = sorted((generateRandomList(25)))
print(elements)
searchTerm = float(getItem())

print('-----')
print('Binary Search')
location = binarySearch(elements,searchTerm)
searchResult(searchTerm,'',location)


print('-----')
print('Binary Search Left')
#elements = [1, 2, 2, 2, 4, 4, 4, 4, 5, 6, 7, 8, 9]
#print(elements)
location = binarySearchSame(elements,searchTerm,-1)
searchResult(searchTerm,'',location)

print('-----')
print('Binary Search Right')
location = binarySearchSame(elements,searchTerm,1)
searchResult(searchTerm,'',location)



print('-----')
print('Binary Search Closest')
closest, location = binarySearchClosest(elements,searchTerm)
searchResult(searchTerm,closest, location)