def Binary_search(A, x):
    """Бинарный поиск
    T(n) = T(n/2) + c <==> O(log n)"""
    """Вход: отсортированный массив. Смотрим в середину, сравниваем, сдвигаем границы поиска в сторону, где элемент
    может быть, повторяем пока не нашли."""
    b = 0
    e = len(A)
    while b < e:
        m = int((b + e)/2)
        if A[m] == x:
            return m
        elif A[m] < x:
            b = m + 1
        else:
            e = m
    return -1  # Если не найдено


a = [1, 5, 8, 50, 59, 100, 250, 500]

print(Binary_search(a, 5))
