32
правки
Изменения
Нет описания правки
Когда будем обрабатывать следующий запрос, то проинициализируем левую границу как <tex>startL</tex>.
Заметим, что все элементы, которые лежат не правее <tex>startL</tex>, строго меньше текущего искомого элемента, так как они меньше предыдущего запроса, а значит и меньше текущего. Значит инвариант цикла выполнен.
== Применение двоичного поиска на неотсортированных массивах ==
'''Применение поиска на циклически сдвинутом отсортированном массиве'''
Пусть отсортированный массив, все элементы которого различны, был циклически сдвинут, тогда новый полученный массив состоит из двух отсортированных. Используем двоичный поиск, чтобы найти индекс последнего элемента первого из этих массивов. Для этого, в реализации двоичного поиска заменим условие в <tex>if</tex> на <tex>a[m] > a[n]</tex>, тогда в <tex>r</tex> будет содержаться искомый индекс. Далее мы можем воспользоваться двоичный поиском искомого элемента <tex>key</tex>, просто запустив его два раза: на массиве <tex>[0, r]</tex> и массиве <tex>[r + 1, n]</tex>.
== См. также ==
