Изменения
→Код
Для простоты дальнейших определений будем считать, что <tex>a[-1] = -\infty</tex> и что <tex>a[n] = +\infty</tex> (массив нумеруется с <tex>0</tex>).
{{Определение|definition='''Правосторонний бинарный поиск''' (англ. <i>rightside binary search</i>) {{---}} бинарный поиск, с помощью которого мы ищем <tex> \max\limits_{i \in [-1,n-1]} \{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>[1;4]</tex>, то есть <tex>4</tex>.
Если искомого элемента в массиве нет, то правосторонний поиск выдаст минимальный максимальный элемент, больший меньший искомого, а левосторонний наоборот, максимальный минимальный элемент, меньший больший искомого.
== Алгоритм двоичного поиска ==
r = m <font color="green">// Сужение границ</font>
'''return''' r
Инвариант цикла: правый индекс не меньше искомого элемента, а левый {{---}} строго меньше (т.к значение <tex>m</tex> присваевается левой границе <tex>l</tex>, только тогда, когда <tex>a[m]</tex> строго меньше искомого элемента <tex>key</tex>), тогда если <tex>r = l + 1</tex> (что эквивалентно <tex>r-l=1</tex>), то понятно, что <tex>r</tex> {{---}} самое левое вхождение искомого элемента (так как предыдущие элементы уже меньше искомого элемента)
В случае правостороннего поиска изменится знак сравнения при сужении границ на <tex>a[m] \leqslant k</tex>.
== Несколько слов об эвристиках ==
