import math
## Program to undertake a binary search
names = ["Alfi", "Amara", "Amisha", "Carla", "Criselle", "Jemima", "Jemimah",
"Kemi", "Maria", "Mia", "Mona-Lisa", "Nayana", "Ollie", "Ore", "Racheal",
"Tiffany"]
# Ask the user what they want to search for
searchItem = input("What are you looking for?")
found = False
while not found:
# Find the midpoint
## If there are 5 things in the list, the midpoint is the 3rd item.
## If there are 6 things in the list, the midpoint is the 4th item (choosing to always go up)
## Medians can be found using the formula (n + 1)/2
## The 'ceil' function in math will be useful here - import math
## How will we reference the position in the array we need?
midpoint = math.ceil((len(names)+1)/2) - 1
# Check the list isn't empty
if len(names) == 0:
print("Not in the list :(")
found = True # to end the while loop
else:
print(f"Comparing {names[midpoint]} with {searchItem}")
# Check the midpoint value against the search item - does it match?
if names[midpoint] == searchItem:
print("Found it!")
found = True
# Otherwise discard half of the list
elif searchItem > names[midpoint]:
names = names[midpoint + 1:] # Start one up from midpoint, go to end
print(names)
else:
names = names[:midpoint] # Start at 0, go to midpoint
print(names)
# repeat
## We don't know how many times this will happen
## Use a flag to symbolise whether the item has been found or not.