Изменения

Пусть нам задана монотонная функция. Необходимо найти место, где значение (<tex>c</tex>) этой функции становится меньше, чем какое-то заданное значениев заданной точке (<tex>x</tex>).<br>[[Файл:FunctsiaFunction.GIFpng]]

Применим идею двоичного поиска. Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границув середину отрезка. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Встает вопрос, когда остановиться. Есть несколько способов сделать это.

== Выбор границы Способы закончить поиск ==Для начала найдем правую границу. Выберем произвольную положительную точку (например 1). Будем удваивать ее до тех пор, пока значение функции * Первый способ заключается в этой точке меньше заданного. Для тоготом, чтобы найти левую границу выберем произвольную отрицательную точку. Будем удваивать ее до тех поростановиться, пока значение в ней будет больше когда рассматриваемый отрезок станет меньше заданного значенияэпсилон.Но у этого подхода есть свои плюсы и минусы:: <tex>\oplus</tex> Алгоритм с большой точностью найдет значение аргумента

== Способы закончить поиск ==# Первый способ заключается в том, чтобы остановиться, когда рассматриваемый отрезок станет меньше заданного эпсилон. Но у этого подхода есть свои плюсы и минусы:#* Алгоритм с большой точностью найдет значение аргумента#* <tex>\ominus</tex> Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел. У чисел есть точность. Соответственно при больших значениях функции, длина отрезка может никогда не уменьшиться до заданного значения# * Второй способ менее точен. Предлагается заканчивать алгоритм, когда значение функции на концах отрезках различается менее, чем на заданное эпсилон.#* : <tex>\oplus</tex> В отличии от предыдущего, не зацикливается при больших значениях функции.#* : <tex>\ominus</tex> Возможна большая погрешность, если функция будет очень медленно возрастать# * Абсолютно точный поиск. Вспомним о том, что вещественный числа в компьютере дискретным. Будем завершать поиск, когда границы отрезка - два соседних по представлению значения в типе данных. Утверждается, что два числа - соседние, если середина их отрезка совпадает или с левой, или с правой границей.#* : <tex>\ominus</tex> Возможно плохое поведение, если искомый аргумент равен 0.# * Итеративный способ. В этом способе выполниться только конечное число число итераций.#* : <tex>\oplus</tex> Плюсом этого способа является фиксированная погрешность. == Выбор границы отрезка для поиска==Для начала найдем правую границу. Выберем произвольную положительную точку (например </tex>1</tex>). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного. Для того, чтобы найти левую границу выберем произвольную отрицательную точку (например <tex>-1</tex>). Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения.

l left = mid;

r right = mid;