10
правок
Изменения
Нет описания правки
== Алгоритм двоичного поиска ==
[[Файл:shcemebinsearch.png|350px|thumb|right|Схема бин. бинарного поиска]]
Идея поиска заключается в том, чтобы брать элемент посередине, между границами, и сравнивать его с искомым.
== Код ==
Инвариант цикла: пусть левый индекс не больше искомого элемента, а правый {{---}} строго больше, тогда если <tex>l = r - 1</tex>, то понятно, что <tex>l</tex> {{---}} самое правое вхождение (так как следующее уже больше).
== Несколько слов об эвристиках ==
'''Эвристика с завершением поиска, при досрочном нахождении искомого элемента'''
Заметим, что если нам необходимо просто проверить наличие элемента в упорядоченном множестве, то можно использовать любой из правостороннего и левостороннего поиска.
При этом давайте будем на каждой итерации проверять "не попали ли мы в элемент, равный искомому", и в случае попадания заканчивать поиск.
'''Эвристика с запоминанием ответа на предыдущий запрос'''
Пусть дан отсортированный массив чисел, упорядоченных по неубыванию.
Также пусть запросы приходят в таком порядке, что каждый следующий не меньше, чем предыдущий.
Для ответа на запрос будем использовать левосторонний двоичный поиск.
При этом после того как обработался первый запрос, запомним чему равно <tex>l</tex>, запишем его в переменную <tex>start\_l</tex>.
Когда будем обрабатывать следующий запрос, то проинициализируем левую границу как <tex>start\_l</tex>.
Заметим, что все элементы, которые лежат не правее <tex>start\_l</tex>, строго меньше текущего искомого элемента, так как они меньше предыдущего запроса, а значит и меньше текущего. Значит инвариант цикла выполнен.
== См. также ==
