binary_search_nearest

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,1,1,2,3,5,6,7,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 or mid-1 == 0:
        return 0
      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 statements for debugging
  print("Search value not found; returning next closest value!")
  r = abs(value - float(dataset[right]))
  #print r
  l = abs(value - float(dataset[left]))
  #print l
  #print mid
  if mid == 0:
    return mid
  elif r < l:
    return right
  else:
    return left

  #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("Float:", guess)
#print("Rounded:", query)
search = binary_search(sorted_list, guess)

#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("Original list was:", start_list)
print("Sorted list:", sorted_list)