61
правка
Изменения
м
Нет описания правки
'''Вещественный двоичный поиск''' {{- --}} алгоритм поиска аргумента для заданного значения монотонной вещественной функции.
== Формулировка задачи ==
: – Возможна большая погрешность, если функция будет очень медленно возрастать
* Абсолютно точный поиск. Вспомним о том, что вещественный числа в компьютере дискретным. Будем завершать поиск, когда границы отрезка {{- --}} два соседних по представлению значения в типе данных. Утверждается, что два числа {{--- }} соседние, если середина их отрезка совпадает или с левой, или с правой границей.
: '''+''' Алгоритм найдет число с максимально возможной точностью.
: – Возможно плохое поведение, если искомый аргумент равен 0.
</pre>
== Пример использования ==
Классической задачей на вещественный двоичный поиск является задача поиска корня <tex>n</tex>-ой степени из числа <tex>x</tex>: <tex>\sqrt[n]{x}</tex>. При <tex>x \ge 1</tex> нижней границей для поиска будет <tex>1</tex>, а верхней {{- --}} <tex>x</tex>.
== Замечания ==
Необходимо отметить, то функция должна быть строго монотонна, иначе данный алгоритм не найдет искомый аргумент, либо найдет аргумент, но он не будет единственным. Важным отличием от целочисленного поиска является то, что мы передвигаем границу ровно в середину отрезка (<tex>left = mid</tex>), а не со смещением внутрь отрезка (<tex>left = mid + 1</tex>).
== Источники ==
* [http://www.intuit.ru/department/algorithms/basicalgos/2/ Интернет университет, лекция сортировка и поиск]
