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