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