Изменения

{{Определение|definition='''Целочисленный двоичный поиск (бин. бинарный поиск) <i>(от англ. Binary Searchbinary search)</i>''' {{---}} алгоритм поиска объекта по заданному признаку во в множестве объектов, упорядоченных по тому же самому признаку, работающий за логарифмическое время. }}

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

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

Когда мы ищем правосторонним бинарным поискомДля простоты дальнейших определений будем считать, то он возвращает индекс самого правого вхождения заданного значения что <tex> x a[0] = -\infty</tex> и что <tex>a[n] = +\infty</tex> .

Когда же {{Определение|definition='''Правосторонний бинарный поиск левосторонний<i>(англ. rightside binary search)</i>''' {{---}} бинарный поиск, с помощью которого мы ищем <tex> \max\limits_{i \in [0,n]}(i | a[i] \leqslant x) </tex>, возвращается индекс самого левого вхождения заданного значения где <tex>a</tex> {{---}} массив, а <tex> x </tex> .{{---}} искомый ключ}}

Это разделение помогает находить количество подряд идущих равных значений{{Определение|definition='''Левосторонний бинарный поиск <i>(англ.leftside binary search)</i>''' {{---}} бинарный поиск, с помощью которого мы ищем <tex> \min\limits_{i \in [0,n]}(i | a[i] \geqslant x) </tex>, где <tex>a</tex> {{---}} массив, а <tex>x</tex> {{---}} искомый ключ}} Использовав эти два вида двоичного поиска, мы можем найти интервал позиций <tex>[l,r]</tex> таких, что <tex>\forall i \in [l,r] : a[i] = x</tex> и <tex> \forall i \notin [l,r] : a[i] \neq x </tex>