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

Пусть $f:\{l,l+1,\dots ,r-1,r\}\to \{0,1\}$ (функция, которая которая на области определения $[l,r]$ имеет область значений $\{0,1\}$ и $f$ монотонная на этой области.

Всё что обсуждалось в предыдущей главе про целочисленный поиск работает и тут, так как область значений является аналогом отсортированного массива. Такой поиск называется вещественный, так как функция $f(x)$ похожа на математическую функцию. Главное, чтобы функция была монотонной.

Идея та же, что и при целочисленном бинарном поиске : сначала возьмём такие границы поиска $l=L,r=R$. После этого на каждом шаге будем сдвигать одну из границ $l,r$, в зависимости от значения $f\left(\frac{l+r}{2}\right)$. В тот момент, когда $l$ и $r$ отличаются на единицу, $r$ — искомый порог. Если считать, что значение функции в точке вычисляется за $O(1)$, то время работы алгоритма — $O({\log }_2(R-L))$, где $L,R$ — начальные границы поиска.

Разовьём идею дальше, можно искать не только целочисленные точки, но и дробные!!! Увы, большой точности добиться невозможно. Проблема заключается в том, что действительные числа хранятся в компьютере неточно(. Например, если ответ это число $\pi$. Для границ стоит использовать тип с самой большой точностью, в c++ это тип double.

Тем не менее, мы можем найти такое $x$ с погрешностью $ϵ$: найдём такое $x$, что существует $x^{\prime }$ такое, что $f(x^{\prime })=0,|x-x^{\prime }|<ϵ$. Единственное отличие от обычного бинпоиска : мы завершаем алгоритм в тот момент, когда $r-l<ϵ$.

Время работы алгоритма (при условии, что значение $f$ вычисляется за $O(1)$ — $O\left({\log }_2\left(\frac{R-L}{ϵ}\right)\right)$.

Любой алгоритм целочисленного поиска, является подмножеством вещественного, в котором функция бинарная. Например, для проверки есть ли число в массиве, надо было лишь заменить if (a[mid] < x) на $f(mid,x)=a[mid]<x$.