Вещественный двоичный поиск

Вещественный двоичный поиск — алгоритм поиска аргумента для заданного значения монотонной вещественной функции.

Формулировка задачи

Пусть нам задана монотонная функция. Необходимо найти значение аргумента [math]x[/math] этой функции, в которой она принимает определенное значение [math]C[/math].

Решение задачи

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

Способы закончить поиск

Способы	Плюсы	Минусы
1) Окончание, когда рассматриваемый отрезок станет меньше заданного эпсилон.	Заданная точность найденного значения.	Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел. У чисел есть точность. Соответственно, при больших значениях функции длина отрезка может никогда не уменьшиться до заданного значения.
2) Окончание, когда значение функции на концах отрезках различается менее, чем на заданное эпсилон.	Значение функции от найденного значения имеет заданную точность.	а) Возможна большая погрешность, если функция будет очень медленно возрастать. б) Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел. У чисел есть точность. Соответственно, при быстром возрастании значений функции мы можем не найти такие границы, что значение на них различается менее, чем на заданное эпсилон.
3) «Абсолютно точный поиск» Окончание, когда границы отрезка — два соседних по представлению значения в типе данных. Утверждается, что два числа — соседние, если середина их отрезка совпадает или с левой, или с правой границей.	Максимально возможная точность найденного значения.	Возможно плохое поведение, если искомый аргумент равен 0.
4) «Итеративный способ» Выполнение конечного числа итераций.	У способа фиксированная погрешность.	Довольно плохая точность, если границы отрезка находятся на большом расстоянии.

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

Для начала найдем правую границу. Выберем произвольную положительную точку (например [math]1[/math]). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного. Для того, чтобы найти левую границу выберем произвольную отрицательную точку (например [math]-1[/math]). Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения.

Псевдокод

findLeft(c): 
    x = -1
    while f(x) > c 
        x = x * 2
    return x 

findRight(c):
    x = 1
    while f(x) < c
        x = x * 2
    return x

binSearch(c):
    left = findLeft(с)
    right = findRight(с)
    while left < right - eps                           //Здесь можно использовать другое условие выхода
        mid = (left + right) / 2
        if f(mid) == c                                 //**
            return mid                                //**
        else if f(mid) < c
            left = mid
        else
            right = mid
    return l

Примеры использования

• Классической задачей на вещественный двоичный поиск является задача поиска корня [math]n[/math]-ой степени из числа [math]x[/math]: [math]\sqrt[n]{x}[/math]. При [math]x \ge 1[/math] нижней границей для поиска будет [math]1[/math], а верхней — [math]x[/math].
• Если функция нестрого монотонна, то, убрав из приведенного выше алгоритма строки, отмеченные [math](**)[/math], мы получим алгоритм, который будет находить [math]x[/math] такой, что [math]f(x) = c[/math] и [math]f(x - \epsilon) \lt c[/math].

Замечания

• Необходимо отметить, то функция должна быть строго монотонна, если мы ищем конкретный корень и он единственный. Нестрого монотонна, если нам необходимо найти самый левый (правый) аргумент. Если же функция не монотонна, то данный алгоритм не найдет искомый аргумент, либо найдет аргумент, но он не будет единственным.
• Важным отличием от целочисленного поиска является то, что мы передвигаем границу ровно в середину отрезка ([math]left = mid[/math]), а не со смещением внутрь отрезка ([math]left = mid + 1[/math]).

Источники

• Интернет университет, лекция сортировка и поиск