65
правок
Изменения
м
Нет описания правки
<code>
<font color="green">// Поиск последнего элемента левого массива</font>
'''int''' a = 0
'''int''' b = n + 1
'''function''' indexOfLastLeftArrayElement('''int''' a,'''int''' b)
'''int''' l = a
Проверим, равен ли <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(\log^2 n)</tex> (мы запускаем бинарный поиск, который требует <tex>O(\log n)</tex> времени <tex>O(\log n)</tex> раз).
==='''Применение поиска на циклически сдвинутом массиве, образованном приписыванием отсортированного по убыванию массива в конец отсортированного по возрастанию'''===
