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