Изменения

Пусть отсортированный по неубыванию массив<tex>a[0..n]</tex>, все элементы которого различны, был циклически сдвинут, тогда новый полученный массив состоит из двух отсортированныхчастей. Используем двоичный поиск, чтобы найти индекс последнего элемента первого из этих массивовпервой части массива. Для этого, в реализации двоичного поиска заменим условие в <tex>if</tex> на <tex>a[m] > a[n]</tex>, тогда в <tex>rl</tex> будет содержаться искомый индекс:<code> '''int''' l = 0 '''int''' r = n + 1 '''while''' l < r - 1 <font color="green">// Запускаем цикл...</font> m = (l + r) / 2 <font color="green">// m {{---}} середина области поиска.</font> '''if''' a[m] < a[n] <font color="green">// Сужение границ..</font> l = m '''else''' r = m '''int''' x = l <font color="green">// x {{---}} искомый индекс. Далее мы можем воспользоваться двоичный </font></code>Затем воспользуемся двоичным поиском искомого элемента <tex>key</tex>, просто запустив его два разана каждой части массива: на массиве <tex>[0, rx]</tex> и массиве на <tex>[r x + 1, n]</tex>.