Лекция 2. Упражнение 1

""" Написать реализацию бинарного поиска на Python.
    Имеется отсортированный список из 148 имен, и вы ищете в нем
    значение методом бинарного поиска."""
# count = 1
def binary_search(li, key):
    # global count
    low = 0  # Нижняя граница
    up = len(li)  # Верхняя граница

    while low <= up:
        cent = (up + low) // 2  # Берём целую воловину
        # count += 1

        if li[cent] == key:
            return cent  # Возвращаем индекс
        if li[cent] > key:
            up = cent - 1
        elif li[cent] < key:
            low = cent + 1
    return -1  # Не встречалось


data = [i for i in range(1, 149)]  # Допустим, вместо имён я буду использовать цифры

print(binary_search(data, 1))  # 150 --> 1
# print(count)

"""
    Какое максимальное количество проверок для этого может потребоваться?
           Ответ: используя формулу log2 148 и округляю в большую сторону получим: 8
           2^7 < 148 < 2^8

           Также можно проверить через программу написанную выше, раскомментировав
           закомментированные части и введя 1

    Предположим, размер списка увеличился вдвое. Как изменится максимальное количество
    проверок? 148 --> 296
           Ответ: Всё та же формула log2 296, всё также округляю в большую сторону: 9
           2^8 < 296 < 2^9

           Всё также можно проверить через программу.
"""