binary_search_right+left

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, 4, 4, 4, 4, 4, 5, 6, 7, 8, 9]


#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

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

    #return the rightmost item if value repeated
    elif dataset[mid] == value and dataset[mid + 1] == value:
      left = mid + 1
      right = 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, "isolated at position", search)
else:
  print(guess, "not found.")

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