Изменения
→Код
}}
==Принцип работы==
Двоичный поиск заключается в том, что на каждом шаге множество объектов делится на две части и в работе остаётся та часть множества, где находится искомый объект. Или же, в зависимости от постановки задачи, мы можем остановить процесс, когда мы получим первый или же последний индекс вхождения элемента. Последнее условие {{---}} это левосторонний/правосторонний двоичный поиск.
== Правосторонний/левосторонний целочисленный двоичный поиск ==
Использовав эти два вида двоичного поиска, мы можем найти отрезок позиций <btex>[l,r]</tex> таких, что <tex>\forall i>Например\in [l,r] :a[i] = x</tex> и <tex> \forall i \notin [l,r] : a[i>] \neq x </btex>
Отсюда следует, что количество подряд идущих двоек равно длине отрезка <tex>[1;4]</tex>, то есть <tex>4</tex>. Если искомого элемента в массиве нет, то правосторонний поиск выдаст минимальный максимальный элемент, больший меньший искомого, а левосторонний наоборот, максимальный минимальный элемент, меньший больший искомого.
== Алгоритм двоичного поиска ==
Идея поиска заключается в том, чтобы брать элемент посередине, между границами, и сравнивать его с искомым.
== Код ==
== См. также ==
* [[Интерполяционный_поиск|Интерполяционный поиск]]
== Источники информации == *Д. Кнут {{- --}} Искусство программирования (Том 3, 2-е издание) ==Ссылки==* [http://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA Википедия {{- --}} двоичный поиск]* [http://habrahabr.ru/post/146228/ Типичные ошибки при написании бинарного поиска]* [http://algolist.manual.ru/search/advbin.php Бинарный поиск на algolist]
== Примечания ==
<references/>
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы поиска]]