Бинарный поиск. Практика

Рассмотрим задачу:
Найти корень уравнения \(x^2 + \sqrt x = C\). Это монотонно возрастающая функция, определенная для неотрицательных значений
С помощью компьютера точное значение найти невозможно. Оценим возможные подходы.
Пусть:

•  \(x_0 : x_0^2 + \sqrt{x_0} = C\) - корень уравнения
•  \(x_L : x_L <= x_0, x_L^2 + \sqrt{x_L} = C_L\) - найденная оценка "слева"
•  \(x_R : x_R >= x_0, x_R^2 + \sqrt{x_R} = C_R\) - найденная оценка "справа"
• acc - параметр, определяющий достаточную точность (положительное число)

Какие варианты постановки задач могут быть:

1.  Абсолютная точность (по аргументу), то есть требование \(|x_R - x_L| \leq acc\) (Например: с точностью не менее 0,001/трех знаков после запятой)
   Условие \(|x_R - x_L| \leq acc\) с учетом \(x_L \leq x_0 \leq x_R\) гарантирует \(|x_0 - x_L| \leq acc;\ \ |x_0 - x_R| \leq acc \)
2.  Абсолютная погрешность (по значению), то есть требование \(|С_R - С| \leq acc\)  и/или \(|С_L - С| \leq acc\) (Например: с погрешность не менее 0,001/трех знаков после запятой)
   Для монотонных функций можно использоваить \(|С_R - С_L| \leq acc\)
3.  Относительная точность (по аргументу), то есть требование \(\frac{|x_R - x_0| }{|x_0|}\leq acc; \frac{|x_L - x_0| }{|x_0|}\leq acc; \) (Например: с точностью не менее 6 знаков)
   Поскольку значение корня неизвестно, то требование можно усилить, потребовав выполнение совпадения знаков для   \(x_R , x_L\), то есть \(\frac{|x_R - x_L| }{|x_L|}\leq acc; \frac{|x_L - x_R| }{|x_R|}\leq acc; \)
4. Относительная погрешность (по значению), то есть требование \(\frac{|С_R - С|}{|C|} \leq acc\)  и/или \(\ \ \frac{|С_L - С|}{|C|} \leq acc\) (Например: с погрешность не менее шести знаков)

Условия точности определяют количество шагов бинарного поиска и типа используемых аргументов.
Так, если С имеет порядок 10¹⁰,  то требование абслоютной погрешности не менее 6 знаков, есть требование получения более 10 точных знаков.
(при С порядка 10²⁰ с переменными типа double не выполнимо). Таким образом, наиболее разумным,  является требование относительной точности/погрешности

Рассмотрим задачу:
Найти корень уравнения \(x^2 + \sqrt x = C\). Это монотонно возрастающая функция, определенная для неотрицательных значений

Как определить, что  для заданного значения аргумента значение функции больше/меньше/равно заданному значению C?
Простым вычислением это  не всегда будет верно, Так . Например

Пример 1 (квадрат принят за квадрат, причем меньший)	Пример 2 (не квадрат принят за квадрат, причем больший по значению)
x = 9007199255000001 y = x * x  print(y**0.5) выведет значение 9007199255000000.0	x = 123456789 y = x * x - 1 print(y**0.5) выведет значение 123456789

Это связано с ограниченной точность вычислений в вещественных чисел
Часто проверку можно провести в целых числах (актуально для реализации на Python) или без использования фyкций специальных библиотек

Рассмотрим зададу "Провода"
Дано N отрезков провода длиной L1, L2, ..., LN сантиметров.
Требуется с помощью разрезания получить из них K равных отрезков как можно большей длины,
выражающейся целым числом сантиметров. Если нельзя получить K отрезков длиной даже 1 см, вывести 0.
Задача на оптимизацию, по набору от параметра K. Практическое решение задачи несложно, если применить 
метод Бинарного поиска по ответу (BSA). Суть метода в том, что

1. Если можно разрезать на K кусков длины L, то можно разрезать и на K кусков меньшей длины
2. Если нельзя разрезать на K кусков длины L, то нельзя разрезать и на K кусков большей длины
3.  Количество вариантов ответа конечно (от 1 до максимальной длины отрезка)
4.  Если зафиксировать длину отрезка L, то несложно найти K_L - число кусков, которые можно получить.

Значит, если определить функция KL, то это будет монотонная функция, для которой несложно найти ответ с помощью
бинарного поиска
Решение задания можно организовать с помощью рекурсии  с использованием программ

• auto solve(const vector <int> & D, M); - возвращающей количество отрезков длины M, которые можно получить из набора длин 
• auto bsa(int L,int R, const vector <int> & D, int K) - возвращающий ответ на задание, где
  L - достижимое значение длины (инициализируем 1, если сумма длин всех отрезков не меньше K)
  R - значение длины, которое  нельзя получить (инициализируем  любым значение большим максимальной длины отрезка)
  D - набор длин отрезков
  K - количество отрезков которое надо получить 

Пояснение к решению
1. Найдите лучшие приближения "слева" (значение выражения < 0) и "справа" (значения выражения \(\geq 0\))
2. Сравните абсолютные значения этих выражений. Без использования операций **, pow, sqrt это можно сделать так
пусть X_l, Y_l  - решение "слева", а X_r, Y_r - решение справа. Тогда
\(|\sqrt a\cdot X_l + \sqrt b\cdot Y_l| \leq |\sqrt a\cdot X_r + \sqrt b\cdot Y_r| <=> \\ a\cdot (X_l^2 - X_r^2) + b\cdot( Y_l^2 - Y_r^2) \leq 2\sqrt {a\cdot b}(X_r\cdot Y_r- X_l\cdot Y_l) \)
вычислив \(|z_1 =a\cdot (X_l^2 - X_r^2) + b\cdot( Y_l^2 - Y_r^2);\ z_2 =(X_r\cdot Y_r- X_l\cdot Y_l) \) 
и сравнив знаки z₁ ,z₂  можно определить какое из значений лучше

Бинарный поиск применяется для решения широкого класса задач и  способы его реализации бывают разные. 
Рассмотрим следующую задачу.
Необходимо найти точку пересечения отрезка AB и сферы радиуса R, с центром в точке O 
(Гарантируется, что внутри сферы находится только одна из границ отрезка. Будем считать, что внутри сферы точка A).
Можно, конечно, найти аналитическое решение, но 

• во-первых, что даст знание координат точки пересечения?
• во-вторых, аналитическое решение ещё надо реализовать

Проще и практичнее решить задачу бинарным поиском, поскольку

• проверка на то, что точка лежит внутри сферы с заданным центром и радиусом тривиальна
• точки на отрезке можно задавать с помощью отношени (рациональной дроби)
• точность вычислений определять "числом шагов" бинарного поиска.

Определим требования к программам  

1. Программа check(T, O,r)  возвращает 1 если точка T лежит внутри сферы или на сфере, в противном случает возвращает 0
   T, O - кортежи  из трех координат каждый
   r - положительное вещественное число
   правило проверки \((T_x-O_x)^2 +(T_y-O_y)^2 +(T_z-O_z)^2 \leq r^2\) 
2. Программа next_dot(L,R) - возвращает коэффициенты разбиения AB для "средней точки" (M) 
   L, R - коэффициенты "левой" и "правой" границ отрезка (L < R). Коэффициент \(k\ (0\leq k \leq1) \) - определяет точку T на \(\overline {AB}\) "векторным способом \(\overrightarrow{OT} = \overrightarrow{OA} + k\cdot\overrightarrow{AB}\)
   Для практических целей было бы удобно, чтобы k были бы ращиональными дробями. Поэтому задавать парами чисел (числитель, знаменатель)
   Начальными значениями можно считать L = (0,1), R =(1,1) (то есть 0 и 1). Новое значение M можно получать как  (L[0] + R[0], L[1] + R[1] ) .
   (нетрудно проверить, что для натуральных \(a,b,c,d \ из\ \frac{a}{b}<\frac{c}{d} =>\frac{a}{b}<\frac{a+c}{b+d}<\frac{c}{d} \))
   Если \(k = \frac{n}{m}\) - коэффициент разбиения отрезка AB, то координаты точки разбиения есть \((A_x+(B_x-A_x)\cdot\frac{n}{m},A_y+(B_y-A_y)\cdot\frac{n}{m},A_z+(B_z-A_z)\cdot\frac{n}{m})\)
3.  Вопрос "достоверности"/точности можно решить заданием количества шагов разбиений или ограниченим на значение знаменателя дроби разбиения.

Задание можно решать по разному:

1. Метод моделирования - реализовать последовательность и развернуть её требуемую глубину
   (от такого способа нас предостеригают в пояснении к условию)
2. Аналитически - определить формулу N-го члена и вычислить. 
   (это вполне рабочий метод, но как его реализовать)
3. "Практический" - что-то среднее между 1 и 2. При реализации воспользуемся  "восходящим" бинарным поиском по ответу.

Построение последовательности состоит из серий: 

• добавили 1 нечетный
• добавили 2 четных
• добавили 3 четных
• и т.д.

Пусть k-я серия состоит из A_k1, ..., A_kk - тогда очевидно, что A_kk = A_k1 + 2*(k-1)
А если учесть, что A_k1 = A_k-1k-1 + 1. Таким образом A_kk = A_k-1k-1 + 2(k-1) + 1
Это дает следующие ответы:

• номер элемента A_kk равен 1 + 2...+ л = л(л+1)/2
• значение элемент A_kk равно (2*1 -1) +(2*2 - 1) + ... + (2*k -1) = k²

Теперь ясно, как находить  N-й элемент

1. Найти сколько "полных" серий до номера N и значение последнего элемента 
2. Определить номер элемента в серии и добавить необходимое значение

Для поиска числа полных серий можно (полезно в качестве тренировки)

• определить границы интервала "восходящим способом)
  (  while (f(R) <= N) { R*=2;} L = R/2; )
• бинарным поиском найти точное число серий,