Действительный бин-поиск

Пусть нам дали какое-нибудь действительное неотрицательное число $x$ (для простоты посчитаем, что $x \geq 1$) и просят найти $\sqrt{x}$ с какой-нибудь точностью $\varepsilon$.

Идея

Забудем про всякие умные способы поиска корня и про встроенные математические библиотеки. Заметим, что корень монотонен: если $x > y \geq 0$, то $\sqrt{x} > \sqrt{y}$. Это замечание позволяет нам сделать бин-поиск по ответу.

Мы знаем, что $\sqrt{1} = 1 \leq \sqrt{x} < x + 1$. Тогда зададим границы $l = 1, r = x + 1$ и запустим стандартный бин-поиск с парой отличий: делить мы будем честно, а не целочисленно, и условие завершения алгоритма будет иным.

Условие завершения

В целочисленном бин-поиске мы исполняли алгоритм, пока $l$ и $r$ не окажутся на расстоянии $1$ друг от друга. Понятно, что сейчас этот способ нам не подходит. Решение - делить пополам, пока $r - l > \varepsilon$.

Иногда нам нужна не абсолютная точность, а относительная, то есть чтобы наш ответ был в диапозоне $[ans(1-\varepsilon); ans(1+\varepsilon)]$, тогда условие можно изменить на $r - l > \varepsilon l$.

Асимптотика

Вообще говоря, $x$ ограничен: условием задачи, типом данных, в котором его хранят или здравым смыслом.

Изначально $r - l = x$. Мы делим отрезок $[l; r]$ пополам, пока его длина превышает $\varepsilon$. Это значит, что мы сделаем $\log_2 \dfrac{x}{\varepsilon}$ итераций, Сложность работы алгоритма - $O(\log \dfrac{x}{\varepsilon})$.

Реализация

eps = 1e-12  # число взято для примера
l, r = 1, x + 1
while r - l > eps:
    m = (l + r) / 2
    if m * m > x:
        r = m
    else:
        l = m
print(l)

Альтернатива

Другой вариант - заменить цикл while на for с фиксированным числом итераций $n$. В таком случае мы получим абсолютную точность $2^{-n}x$. Это может быть полезно, например, для интерактивных задач, где количество запросов строго ограничено.

Тернарный поиск

Задача: дана функция $f$ и отрезок $[a; b]$. Существует такая точка $x \in [a; b]$, что функция монотонно убывает на $[a; x]$, и возрастает на $[x; b]$. Требуется найти точку экстремума (где убывание переходит в возрастание).

Идея

Хочется написать бинпоиск, но его прикрутить некуда: функция не монотонна на всём отрезке. Теоретически можно было бы написать бинпоиск по производной, чтобы найти её нуль, но:

1. Нулей у производной может быть больше одного даже с такими ограничениями.
2. Нужно ещё взять производную, а это затруднительно, если о самой функции нет информации.

Поэтому мы пойдём другим путём.

Пусть у нас есть две точки $x_1 < x_2$, при этом $f(x_1) < f(x_2)$. Где может находиться $x$ относительно $x_1, x_2$?

Точно не на $[x_2; b]$: если бы $x$ лежал на $(x_2; b]$, то $x_1, x_2$ лежали бы в той части, на которой функция монотонно убывает, но в этих точках данное свойство нарушается. Значит, $f(x_1) < f(x_2) \Rightarrow x \in [a; x_2]$.

Аналогично $f(x_1) > f(x_2) \Rightarrow x \in [x_1; b]$.

Теперь применим идею, схожую с идеей бинпоиска: возьмём границы $l = a, r = b$, и будем с помощью описанного выше свойства уменьшать отрезок $[l; r]$, сохраняя неравенство $l \leq x \leq r$.

На каждом шаге выбираем точки $x_1 = \dfrac{2l + r}{3}, x_2 = \dfrac{l + 2r}{3}$, разделяя таким образом текущий отрезок на $3$ равные части. Если $f(x_1) < f(x_2)$, то ставим $r = x_2$, а иначе - $l = x_1$.

Когда границы сойдутся достаточно близко, любую из них или между ними можно посчитать ответом. Из соображений симметрии мы возьмём середину.

Реализация

l, r = a, b
while r - l > eps:
    x1, x2 = (2 * l + r) / 3, (l + 2 * r) / 3
    if f(x1) < f(x2):
        r = x2
    else:
        l = x1
print((l + r) / 2)

Асимптотика

Каждую итерацию отрезок уменьшается в полтора раза. Это значит, что мы сделаем $\log_{3/2} \dfrac{b - a}{\varepsilon}$ итераций. По аналогии с бинпоиском асимптотика будет $O\left(\log \dfrac{b - a}{\varepsilon}\right)$.