Изменения
Нет описания правки
}}
==Принцип работы==
Двоичный поиск заключается в том, что на каждом шаге множество объектов делится на две части и в работе остается остаётся та часть множества, где находится искомый объект. Или же, в зависимости от постановки задачи, мы можем остановить процесс, когда мы получим первый или же последний индекс вхождения элемента. Последнее условие {{---}} это левосторонний/правосторонний двоичный поиск.
== Правосторонний/левосторонний целочисленный двоичный поиск ==
Использовав эти два вида двоичного поиска, мы можем найти отрезок позиций <tex>[l,r]<b/tex>таких, что <tex>\forall i>Например\in [l,r] :</a[i>] = x</btex> <br>Задан отсортированный массив и <tex>\forall i \notin [1l, 2, 2, 2, 2, 3, 5, 8, 9, 11r] : a[i]\neq x </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]