Вещественный двоичный поиск
Вещественный двоичный поиск - алгоритм поиска аргумента для заданного значения монотонной вещественной функции.
Формулировка задачи
Пусть нам задана монотонная функция. Необходимо найти место, где значение функции становится меньше, чем какое-то заданное значение.
Решение задачи
Применим идею двоичного поиска. Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Встает вопрос, когда остановиться. Есть несколько способов сделать это.
Способы закончить поиск
- Первый способ заключается в том, чтобы остановиться, когда рассматриваемый отрезок станет меньше заданного эпсилон. Но у этого подхода есть свои плюсы и минусы:
* Алгоритм с большой точностью найдет найдет значение аргумента * Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел. У чисел есть точность. Соответственно при больших значениях функции, длина отрезка может никогда не уменьшиться до заданного значения
- Второй способ менее точен. Предлагается заканчивать алгоритм, когда значение функции на концах отрезках различается менее, чем на заданное малое значение.
* В отличии от предыдущего, не зацикливается при больших значениях функции. * Возможна большая погрешность, если функция будет очень медленно возрастать
- Абсолютно точный поиск. Вспомним о том, что вещественный числа в компьютере дискретным. Будем завершать поиск, когда границы отрезка - два соседних значения в типе данных.
