1632
правки
Изменения
м
В случае правостороннего поиска изменится знак сравнения при сужении границ на <tex>a[m] \leqslant k</tex>.
Инвариант цикла: пусть левый индекс не больше искомого элемента, а правый {{---}} строго больше, тогда если В случае правостороннего поиска изменится знак сравнения при сужении границ на <tex>l = r - 1a[m] \leqslant k</tex>, то понятно, что а возвращаемой переменной станет <tex>l</tex> {{---}} самое правое вхождение (так как следующее уже больше).
rollbackEdits.php mass rollback
'''return''' r
Инвариант цикла: правый индекс не меньше искомого элемента, а левый {{---}} строго меньше (т.к значение <tex>m</tex> присваевается левой границе <tex>l</tex>, только тогда, когда <tex>a[m]</tex> строго меньше искомого элемента <tex>key</tex>), тогда если <tex>r = l + 1</tex> (что эквивалентно <tex>r-l=1</tex>), то понятно, что <tex>r</tex> {{---}} самое левое вхождение искомого элемента (так как предыдущие элементы уже меньше искомого элемента)
== Несколько слов об эвристиках ==
Найдем индекс последнего элемента массива, отсортированного по возрастанию, воспользовавшись [[Троичный_поиск|троичным поиском]], затем запустим левосторонний двоичный поиск для каждого массива отдельно: для элементов <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>.
== Переполнение индекса середины ==
