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

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

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

Пусть нам задана монотонная функция. Необходимо найти значение ([math]c[/math]) этой функции в заданной точке ([math]x[/math]).

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

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

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

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

[math]\oplus[/math] Алгоритм с большой точностью найдет значение аргумента

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

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

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

[math]\ominus[/math] Возможна большая погрешность, если функция будет очень медленно возрастать

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

[math]\ominus[/math] Возможно плохое поведение, если искомый аргумент равен 0.

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

[math]\oplus[/math] Плюсом этого способа является фиксированная погрешность.

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

Для начала найдем правую границу. Выберем произвольную положительную точку (например </tex>1</tex>). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного. Для того, чтобы найти левую границу выберем произвольную отрицательную точку (например [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
            left = mid;
        else
            right = mid;
    return l;

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

Классической задачей на вещественный двоичный поиск является задача поиска корня [math]n[/math]-ой степени из числа [math]x[/math]: [math]\sqrt[n]{x}[/math]. При [math]x \gt = 1[/math] нижней границей для поиска будет [math]1[/math], а верхней - [math]x[/math].

Источники

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