Изменения
Нет описания правки
Для простоты дальнейших определений будем считать, что <tex>a[-1] = -\infty</tex> и что <tex>a[n] = +\infty</tex> (массив нумеруется с <tex>0</tex>).
{{Определение|definition='''Правосторонний бинарный поиск''' (англ. <i>rightside binary search</i>) {{---}} бинарный поиск, с помощью которого мы ищем <tex> \max\limits_{i \in [0-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>O(6\log n)=O(\log n)</tex>.
== Переполнение индекса середины ==
В некоторых языках программирования присвоение <code>m = (l + r) / 2</code> приводит к переполнению. Вместо этого рекомендуется использовать <code>m = l + (r - l) / 2;</code> или эквивалентные выражения.<ref>https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html</ref>
== См. также ==
* [http://habrahabr.ru/post/146228/ Типичные ошибки при написании бинарного поиска]
* [http://algolist.manual.ru/search/advbin.php Бинарный поиск на algolist]
== Примечания ==
<references/>
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы поиска]]
