binary_search_closest

from random import randint

#collect user input to determine size of random list
#n = int(input("Size of random number list:"))
#start_list = [randint(0, 100) for i in range(n)]

#demo list for item recognition testing
start_list = [1,2,3,5,6,7]


#sort list
sorted_list = sorted(start_list)

#binary search cuts dataset in half after each iteration until midpoint is equal to value
#(neither greater or less); otherwise loop terminates, and False should be returned as value not present
def binary_search(dataset, value):
  n = len(dataset)
  left = 0
  right = n-1
  while left <= right and left < (n-1) and right > 0:
    mid = int((left + right) / 2)
    if dataset[mid] > value:
      right = mid - 1
    elif dataset[mid] < value:
      left = mid + 1

    #return the leftmost item if value repeated
    #elif dataset[mid] == value and dataset[mid - 1] == value:
      #if mid == 0:
        #return mid
      #else:
        #right = mid - 1
        #left = mid - 1

    #return the rightmost item if value repeated
    elif dataset[mid] == value and dataset[mid + 1] == value:
      if mid >= n:
        return mid
      else:
        left = mid + 1
        right = mid + 1

    else:
      return mid

  #This section is meant to determine whether the value on the left or right side of mid is closer by calculating their absolute difference, then returning the relevant position (mid + or - 1)
  print("Search value not found; returning next closest value!")
  r = abs(dataset[mid] - dataset[right])
  print right
  l = abs(dataset[mid] - dataset[left])
  print left
  if r > l:
    return left
  else:
    return right

  #return mid

#collect user input for value to search for in binary_search function; convert floating point values to integers and store in query for search'
guess = float(input("Value to search for:"))
query = round(guess)

#preview rounding results
print(guess)
print(query)
search = binary_search(sorted_list, query)

#report on whether value found
if search != False:
  print(str(guess), "closest to value", sorted_list[search], "at position", search)
else:
  print(str(guess), "closest to value", sorted_list[0], "at position", search)

#print original and sorted list for user inspection
print(start_list)
print(sorted_list)