Изменения

'''Целочисленный двоичный поиск (бин. поиск)''' {{- --}} алгоритм поиска объекта по заданному признаку во множестве объектов, упорядоченных по тому же самому признаку.

Пусть нам дан упорядоченный массив, состоящий только из целочисленых целочисленных элементов. Нам надо найти в нем индекс, по которому находится искомый элемент, или же мы можем находить интервалы вхождения искомого элемента. Для этой задачи мы и можем использовать двоичный поиск.

Двоичный поиск заключается в том, что на каждом шаге множество объектов делится на две части и в работе остается та часть множества, где находится искомый объект. Или же, в зависимости от постановки задачи, мы можем остановить процесс, когда мы получим первый или же последний индекс вхождения элемента. Последнее условие {{- --}} это левосторонний/правосторонний двоичный поиск.

Когда мы ищем правосторонним бин. поиском, то он возвращает индекс самого правого вхождения заданного значения <btex>хx </btex>.<br> Когда же поиск левосторонний, возвращается индекс самого левого вхождения заданного значения <btex>хx </btex>.<br> Это разделение помогает находить количество подряд идущих равных значений.<br> 

Задан отсортированный массив <tex>[1, 2, 2, 2, 2, 3, 5, 8, 9, 11] <br/tex> Правосторонний поиск двойки выдаст в результате <tex>5</tex>, в то время как левосторонний выдаст <tex>2. <br/tex>. От сюда следует, что количество подряд идущих двоек равно длине отрезка <tex>[2;5] = </tex>, то есть <tex>4. <br/tex>. Если искомого элемента нетув массиве нет, то правосторонний поиск выдаст минимальный элемент, больший искомого, а левосторонний наоборот, максимальный элемент, меньший искомого.

В случае равенства возвращать его, а если искомое больше(в случае правостороннего {{- --}} не меньше), чем элемент сравнения,то сужаем область поиска так, чтобы новая левая граница была равна индексу середины предыдущей области. В противном случае присваиваем это значение правой границе. Проделываем эту процедуру до тех пор, пока правая граница больше левой более чем на <tex>1</tex>, или же пока мы не найдём искомый индекс.

В случае правостороннего поиска изменится знак сравнения при сужении границ на (<tex>a[m] <= \leqslant k</tex>).

Инвариант цикла: пусть левый индекс меньше или равен искомого элемента, а правый — {{---}} строго больше, тогда если <tex>l = r - 1</tex>, то понятно, что <tex>l</tex> — {{---}} самое правое вхождение (так как следующее уже больше).