Модуль: Двоичный поиск для монотонной функции (вещественный поиск)


Задача

1/6

Двоичный поиск для монотонной функции (С++)

Теория Нажмите, чтобы прочитать/скрыть

Вещественный двоичный (бинарный поиск) или двоичный поиск для монотонной функции

Двоичный поиск может использоваться не только для поиска элементов в массиве, но и для поиска корней уравнений и значений монотонных (возрастающих или убывающих) функций.

Пусть нам задана монотонная функция f и какое-то значение C этой функции. Необходимо найти значение аргумента x этой функции, такое, что \(f(x)=C\).
 
Пример возрастающей монотонной функции:


Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу в середину отрезка. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Но есть проблема в том, что, когда остановить поиск. Способо закончить поиск подробно описаны здесь
 
Для примера рассмотрим задачу поиска квадратного корня числа x. Квадратным корнем из числа x (обозначается \(\sqrt x\)) называется такое число y, что \(y^2 = x\).
Сформулируем задачу так: для данного вещественного числа x (\(x >= 1\)) найти квадратный корень с точностью не менее 5 знаков после точки.
 


Выбор границы отрезка для поиска

Так как мы не можем проверять всю бесконечность чисел, надо обозначить границы поиска корня. Для начала найдем левую границу, выберем произвольную отрицательную точку (например: -1). Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения. Для того, чтобы найти правую границу, выберем произвольную положительную точку (например: 1). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного. Мы же в своих примерах будет останавливать поиск, когда рассматриваемый отрезок станет меньше заданной погрешности eps.
 
double findLeftBoard(C : double): 
    x = -1
    while f(x) > C 
        x = x * 2
    return x 
double findRightBoard(C : double):
    x = 1
    while f(x) < C
        x = x * 2
    return x

Либо, если мы точно знаем границы поиска, можем взять за левую границу 1, а верхнюю само число x.

После этого делим текущий отрезок пополам, возводим середину в квадрат и если он больше x, то заменяем верхнюю грань, иначе  нижнюю.
Итоговая реализация:
double binSearch(C : double):
    left = findLeftBoard(C) // начальный отрезок
    right = findRightBoard(C)
    while right - left > eps         // сужаем отрезок поиска ответа до малого eps.
        mid = (left + right) / 2
        if f(mid) < C
            left = mid
        else
            right = mid
    return (left + right) / 2 

Задача

Дано натуральное число x. Вычислите кубический корень из числа.
 
Формат входных данных
Число x – натуральное, не превосходящее \(10^6\).
 
Формат выходных данных
Программа должна вывести единственное число: ответ на задачу с точностью не менее 6 знаков после запятой.
Примеры
Входные данные Выходные данные
1 2 1.259921