mail@pastecode.io avatarunknown
13 days ago
1.6 kB
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",

# 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

        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

            names = names[:midpoint] # Start at 0, go to midpoint

    # repeat
## We don't know how many times this will happen
## Use a flag to symbolise whether the item has been found or not.