1632
правки
Изменения
м
В случае правостороннего поиска изменится знак сравнения при сужении границ на <tex>a[m] \leqslant k</tex>.
Инвариант цикла: пусть левый индекс не больше искомого элемента, а правый {{---}} строго больше, тогда если В случае правостороннего поиска изменится знак сравнения при сужении границ на <tex>l = r - 1a[m] \leqslant k</tex>, то понятно, что а возвращаемой переменной станет <tex>l</tex> {{---}} самое правое вхождение (так как следующее уже больше).
rollbackEdits.php mass rollback
Для простоты дальнейших определений будем считать, что <tex>a[-1] = -\infty</tex> и что <tex>a[n] = +\infty</tex> (массив нумеруется с <tex>0</tex>).
{{Определение|definition='''Правосторонний бинарный поиск''' (англ. <i>rightside binary search</i>) {{---}} бинарный поиск, с помощью которого мы ищем <tex> \max\limits_{i \in [0-1,n-1]} \{i \mid a[i] \leqslant x\} </tex>, где <tex>a</tex> {{---}} массив, а <tex>x</tex> {{---}} искомый ключ}}
{{Определение|definition='''Левосторонний бинарный поиск''' (англ. <i>leftside binary search</i>) {{---}} бинарный поиск, с помощью которого мы ищем <tex> \min\limits_{i \in [0,n]}\{i \mid a[i] \geqslant x\} </tex>, где <tex>a</tex> {{---}} массив, а <tex>x</tex> {{---}} искомый ключ}}
Отсюда следует, что количество подряд идущих двоек равно длине отрезка <tex>[1;4]</tex>, то есть <tex>4</tex>.
Если искомого элемента в массиве нет, то правосторонний поиск выдаст минимальный максимальный элемент, больший меньший искомого, а левосторонний наоборот, максимальный минимальный элемент, меньший больший искомого.
== Алгоритм двоичного поиска ==
'''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>.
== Переполнение индекса середины ==
