Вещественный двоичный поиск
Вещественный двоичный поиск — алгоритм поиска аргумента для заданного значения монотонной вещественной функции.
Формулировка задачи
Пусть нам задана монотонная функция. Необходимо найти значение аргумента этой функции, в которой она принимает определенное значение = valOfFunc.
Решение задачи
Применим идею двоичного поиска. Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу в середину отрезка. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Встает вопрос, когда остановиться. Есть несколько способов сделать это.
Способы закончить поиск
| Способы | Плюсы | Минусы | Оценка на число итераций |
|---|---|---|---|
| Окончание, когда рассматриваемый отрезок станет меньше заданной погрешности . | Заданная точность найденного значения. | Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел, у которых есть точность. При больших значениях функции длина отрезка может никогда не уменьшиться до заданного значения. | В данном случае нам нужно рассмотреть чисел примерное число итераций . |
| Окончание, когда значение функции на концах отрезках различается менее, чем на заданную погрешность . | Значение функции от найденного значения имеет заданную точность. | а) Возможна большая погрешность, если функция будет очень медленно возрастать. б) Может зациклиться по той же причине, что и в первом способе. |
Аналогичная с первым случаем логика, примерное число итераций . |
| «Абсолютно точный поиск» Окончание, когда границы отрезка — два соседних по представлению значения в типе данных. Утверждается, что два числа — соседние, если середина их отрезка совпадает или с левой, или с правой границей. |
Максимально возможная точность найденного значения. | Возможно плохое поведение, если искомый аргумент равен нулю. | При работе с числами с плавающей точкой количество итераций зависит от плотности чисел на данном отрезке. При работе с числами фиксированной точности (= ) количество итераций аналогично первому и второму случаю равно . |
| «Итеративный способ» Выполнение конечного числа итераций. |
У способа фиксированная погрешность. | Довольно плохая точность, если границы отрезка находятся на большом расстоянии. | Выполняется заданное количество итераций. |
Выбор границы отрезка для поиска
Для начала найдем левую границу, выберем произвольную отрицательную точку (например ). Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения. Для того, чтобы найти правую границу, выберем произвольную положительную точку (например ). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного.
Псевдокод
double findLeftBoard(valueOfFunc : double):
x = -1
while f(x) > valueOfFunc
x = x * 2
return x
double findRightBoard(valueOfFunc : double):
x = 1
while f(x) < valueOfFunc
x = x * 2
return x
double binSearch(valueOfFunc : double):
left = findLeftBoard(valueOfFunc)
right = findRightBoard(valueOfFunc)
while right - left < eps // Здесь можно использовать другое условие выхода
mid = (left + right) / 2
if f(mid) < valueOfFunc
left = mid
else
right = mid
return (left + right) / 2
Замечания
- Необходимо отметить, то функция должна быть строго монотонна, если мы ищем конкретный корень и он единственный. Нестрого монотонна, если нам необходимо найти самый левый (правый) аргумент. Если же функция не монотонна, то данный алгоритм не найдет искомый аргумент, либо найдет аргумент, но он не будет единственным.
- Классической задачей на вещественный двоичный поиск является задача поиска корня -ой степени из числа : . При нижней границей для поиска будет , а верхней — .
