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

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

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

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

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

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

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

• Первый способ заключается в том, чтобы остановиться, когда рассматриваемый отрезок станет меньше заданного эпсилон. Но у этого подхода есть свои плюсы и минусы:

+ Алгоритм с большой точностью найдет значение аргумента

– Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел. У чисел есть точность. Соответственно при больших значениях функции, длина отрезка может никогда не уменьшиться до заданного значения

• Второй способ менее точен. Предлагается заканчивать алгоритм, когда значение функции на концах отрезках различается менее, чем на заданное эпсилон.

+ В отличии от предыдущего, не зацикливается при больших значениях функции.

– Возможна большая погрешность, если функция будет очень медленно возрастать

• Абсолютно точный поиск. Вспомним о том, что вещественный числа в компьютере дискретным. Будем завершать поиск, когда границы отрезка — два соседних по представлению значения в типе данных. Утверждается, что два числа — соседние, если середина их отрезка совпадает или с левой, или с правой границей.

+ Алгоритм найдет число с максимально возможной точностью.

– Возможно плохое поведение, если искомый аргумент равен 0.

• Итеративный способ. В этом способе выполнится только конечное число число итераций.

+ Плюсом этого способа является фиксированная погрешность.

– Довольно плохая точность, если границы отрезка находятся на большом расстоянии.

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

Для начала найдем правую границу. Выберем произвольную положительную точку (например [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]).

Источники

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