from random import randint
from timeit import Timer
import math


def binary_search(needle, haystack):
    """
    UKOL 4
    binárním vyhledáváním najde v logaritmickém čase needle v haystack
    """
    return False


def test_binary_search():

    print('TEST KOREKTNOSTI')
    for i in range(100, 0, -1):
        key = randint(-10, 10)
        array = sorted([randint(-10, 10) for _ in range(10)])

        bs_result = binary_search(key, array)
        true_result = key in array

        if bs_result is None:
            print('ERROR: Tvoje funkce binary_search nevrací žádnou hodnotu.')
            return

        if true_result != bs_result:
            if true_result:
                print(f'ERROR: Klíč {key} nebyl v seznamu {array} nalezen.')
            else:
                print((f' ERROR: Klíč {key} v seznamu {array} není. '
                      'Tvoje funkce tvrdí, že tam je.'))
            return
    print('Skvěle, tvoje binární vyhledávání funguje správně!')

    print('TEST RYCHLOSTI')
    array = sorted([randint(-100000, 100000) for _ in range(100000)])
    log_timer = Timer(lambda: binary_search(randint(-100000, 100000), array))
    log_time = log_timer.timeit(number=1000) * 1000
    lin_timer = Timer(lambda: randint(-100000, 100000) in array)
    lin_time = lin_timer.timeit(number=1000) * 1000
    result = log_time < 2 * math.log(lin_time)
    if result:
        print(('Výborně! '
              'Tvoje funkce binary search počítá v logaritmickém čase!'))
    else:
        print('ERROR: Bohužel, tvoje implementace je příliš pomalá!')


test_binary_search()