bin_search_complex_function.py

# f(x) = x*x*x + a*x + b; a, b > 0, x - integer
# find x0, such that f(x0) = c, c > 0
​
# Для начала найдем левую границу, выберем произвольную отрицательную точку (например -1). 
# Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения. 
# 
# Для того, чтобы найти правую границу, выберем произвольную положительную точку (например 1).
# Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного.
​
def findLeftBoard(C): 
    x = -1
    while f(x) > C 
        x = x * 2
    return x 
​
def findRightBoard(C):
    x = 1
    while f(x) < C
        x = x * 2
    return x
​
def binSearch(C):
    left = findLeftBoard(C)
    right = findRightBoard(C)
    while right - left > 1: 
        mid = (left + right) / 2
        if f(mid) >= C
            right = mid
        else
            left = mid
    if f(right) == C:
		return right