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