Изменения

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

{{Определение|definition='''Правосторонний бинарный поиск ''' (англ. <i>(англ. rightside binary search)</i>''' ) {{---}} бинарный поиск, с помощью которого мы ищем <tex> \max\limits_{i \in [0,n]}(\{i | \mid 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 | \mid 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>

'''int''' binSearch('''Objectint[]''' a, '''Objectint''' key) <font color="green">// l, r - левая и правая границы</font>

m = (l + r) / 2 <font color="green">// m {{- --}} середина области поиска</font>

При этом давайте будем на каждой итерации проверять "не попали ли мы в элемент, равный искомому", и в случае попадания заканчивать поиск.