binary_search

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 = [9,8,7,6,5,4,3,2,1,0]

#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:
    mid = int((left + right) / 2)
    if dataset[mid] > value:
      right = mid - 1
    elif dataset[mid] < value:
      left = mid + 1
    else:
      return mid+1
  return False

#collect user input for value to search for in binary_search function
guess = int(input("Value to search for:"))
search = binary_search(sorted_list, guess)

#report on whether value found
if search != False:
  print(guess, "found at position", search)
else:
  print(guess, "not found.")

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