Solution for Ex20 on www.practicepython.org

Ex20.py

"""
Write a function that takes an ordered list of numbers (a list where the elements are in order from smallest to
largest) and another number. The function decides whether or not the given number is inside the list and returns
(then prints) an appropriate boolean.

Extras: Use binary search.

NOTE: I created an option to compare the time taken by three different search methods.
"""
import random, time, sys


def main():
    # Setup the data to search in, and search for
    while True:
        qty = input('How many items do you want in your list? (One or more) >  ')  # length of random list, can't be 0
        if qty.isnumeric() and not qty == '0':
            qty = int(qty)
            break

    while True:
        # Set the range from which list will be populated
        max_number = input('Random number choice should be between 1 and...? >  ')
        if max_number.isnumeric():
            max_number = int(max_number)
            break

    start = time.perf_counter()  # Start timing for performance measuring
    my_list = []
    try:
        print('Generating list. KeyboardInterrupt to stop')  # Use KeyboardInterrupt to quit if it's taking too long
        for i in range(qty):
            my_list.append(random.randint(0, max_number))
        my_list.sort()

        end = time.perf_counter()  # End timing
        print('list generated in {} secs'.format(calc_elapsed_time(start, end)))
    except KeyboardInterrupt:
        end = time.perf_counter()
        print('Exiting after {} secs with {} items in list'.format(calc_elapsed_time(start, end), len(my_list)))
        sys.exit()

    while True:
        target = input('Enter target number: >  ')  # The number our search functions will look for
        if target.isnumeric():
            target = int(target)
            break

    while True:
        print(
            '\nSearch mode:\n1: Simple "if x in list" test\n2: "For i in list" loop\n3: Binary search\n4: All')
        choice = input('Your choice >  ')
        if choice and choice in '1234':
            break

    # Functions are implemented for three different ways of searching, plus an option to try them all against the same
    # data to compare performance. Get the desired method:
    if choice == '1':
        result, elapsed = check_number_using_isin(my_list, target)  # Use "if x is in list" syntax
    elif choice == '2':
        result, elapsed = check_number_using_forloop(my_list,
                                                     target)  # Loop through the list, test for equivalence with target
    elif choice == '3':
        result, elapsed = check_number_using_binary_search(my_list, target)  # Use a binary search
    elif choice == '4':
        results = {}
        print('getting results using "x in list" function...')
        results['"x in list"'] = check_number_using_isin(my_list, target)
        print('getting list using "for i in list" method...')
        results['"for i in loop"'] = check_number_using_forloop(my_list, target)
        print('getting list using binary search function...')
        results['"binary search'] = check_number_using_binary_search(my_list, target)

        for k, v in results.items():
            print('{} function returned {}. Operation took {} secs'.format(k, str(v[0]).upper(), v[1]))

    if choice in '123':
        display_result(result, target, elapsed)


def display_result(result, target, elapsed):
    if result:
        t = 'is'
    else:
        t = 'is not'
    print('{} {} in the generated list'.format(target, t))
    print('operation took {} secs'.format(elapsed))


def check_number_using_isin(my_list, target):
    # Use standard "is in" syntax
    start = time.perf_counter()
    if target in my_list:
        result = True
    else:
        result = False
    end = time.perf_counter()
    return result, calc_elapsed_time(start, end)


def check_number_using_forloop(my_list, target):
    # Go through each item in the list in turn, checking if it matches the target number
    start = time.perf_counter()
    result = False
    for i in my_list:
        if i == target:
            result = True
    end = time.perf_counter()
    return result, calc_elapsed_time(start, end)


def check_number_using_binary_search(my_list, target):
    # Use a binary search
    # TODO - rewrite this as a recursive function
    start = time.perf_counter()
    while len(my_list) > 1:
        mid = len(my_list) / 2
        mid = int(mid)
        lower = my_list[0:mid]
        upper = my_list[mid:]

        if target == my_list[mid]:
            end = time.perf_counter()
            return True, calc_elapsed_time(start, end)
        elif target < my_list[mid]:
            my_list = lower
        elif target > mid:
            my_list = upper

    if my_list[0] == target:
        result = True
    else:
        result = False
    end = time.perf_counter()
    return result, calc_elapsed_time(start, end)


def calc_elapsed_time(start, end):
    return end - start


if __name__ == '__main__':
    main()