Изменения
Нет описания правки
== Формулировка задачи ==
Пусть нам дана монотонная функция, значения которой целые числа. Нам необходимо найти место, где функция будет равна заданному значению.
== Выбор границы ==
Нам должны быть заданы границы, на которых мы ищем индекс заданного значения <b>х</b>.
== Правосторонний/левосторонний целочисленный двоичный поиск ==
Когда мы ищем правосторонним бин. поиском, то он возвращает индекс самого правого вхождения заданного значения <b>х</b>.<br>
Когда же поиск левосторонний, возвращается индекс самого левого вхождения заданного значения <b>х</b>.<br>
Это разделение помогает находить количество подряд идущих равных значений.<br>
<b><i>Например:</i></b> <br>
Задан отсортированный массив [1, 2, 2, 2, 2, 3, 5, 8, 9, 11] <br>
Правосторонний поиск двойки выдаст в результате 5, в то время как левосторонний выдаст 2. <br>
От сюда следует, что количество подряд идущих двоек равно длине отрезка [2;5] = 4. <br>
[[Файл:cheme.jpg]]
