1302
правки
Изменения
→Применение двоичного поиска на некоторых неотсортированных массивах: ссылка на тернарный поиск
Найдем индекс последнего элемента массива, отсортированного по возрастанию, воспользовавшись [[Троичный_поиск|троичным поиском]], затем запустим левосторонний двоичный поиск для каждого массива отдельно: для элементов <tex>[0 \ldots x]</tex> и для элементов <tex>[x+1 \ldots n]</tex>, где в качестве <tex>x</tex> мы возьмем индекс максимума, найденный троичным поиском. Для массива, отсортированного по убыванию используем двоичный поиск, изменив условие в <code>'''if'''</code> на <tex>a[m] > key</tex>.
Время выполнения алгоритма {{---}} <tex> O(\log n)</tex> (так как и бинарный поиск, и [[тернарный поиск ]] работают за логарифмическое время с точностью до константы).
Затем, в зависимости от типа нашего массива, запустим бинарный поиск три раза на каждом промежутке.
Время выполнения данного алгоритма {{---}} <tex>O(6\log n)=O(\log n)</tex>.
== Переполнение индекса середины ==
