65
правок
Изменения
м
minor change of indexes
== Правосторонний/левосторонний целочисленный двоичный поиск ==
Для простоты дальнейших определений будем считать, что <tex>a[0-1] = -\infty</tex> и что <tex>a[n+1] = +\infty</tex> (массив нумеруется с <tex>10</tex>).
{{Определение|definition='''Правосторонний бинарный поиск''' (англ. <i>rightside binary search</i>) {{---}} бинарный поиск, с помощью которого мы ищем <tex> \max\limits_{i \in [0,n]} \{i \mid a[i] \leqslant x\} </tex>, где <tex>a</tex> {{---}} массив, а <tex>x</tex> {{---}} искомый ключ}}
Задан отсортированный массив <tex>[1, 2, 2, 2, 2, 3, 5, 8, 9, 11], x = 2</tex>.
Правосторонний поиск двойки выдаст в результате <tex>54</tex>, в то время как левосторонний выдаст <tex>21</tex> (нумерация с единицынуля).
От сюда следует, что количество подряд идущих двоек равно длине отрезка <tex>[21;54]</tex>, то есть <tex>4</tex>.
Если искомого элемента в массиве нет, то правосторонний поиск выдаст минимальный элемент, больший искомого, а левосторонний наоборот, максимальный элемент, меньший искомого.
== Код ==
'''int''' binSearch('''int[]''' a, '''int''' key): <font color="green">// Запускаем бинарный поиск</font>
'''int''' l = 0 -1 <font color="green">// l, r {{---}} левая и правая границы</font> '''int''' r = len(a) + 1
'''while''' l < r - 1 <font color="green">// Запускаем цикл</font>
m = (l + r) / 2 <font color="green">// m {{---}} середина области поиска</font>
Если массив, отсортированный по возрастанию, был циклически сдвнут, тогда полученный массив состоит из двух отсортированных частей. Используем двоичный поиск, чтобы найти индекс последнего элемента левой части массива. Для этого в реализации двоичного поиска заменим условие в <code>'''if'''</code> на <tex>a[m] > a[n-1]</tex>, тогда в <tex>l</tex> будет содержаться искомый индекс:
<code>
'''int''' l = 0-1 '''int''' r = n + 1 len(a)
'''while''' l < r - 1 <font color="green">// С помощью бинарного поиска найдем максимум на массиве</font>
m = (l + r) / 2 <font color="green">// m {{---}} середина области поиска</font>
'''int''' x = l <font color="green">// x {{---}} искомый индекс.</font>
</code>
Затем воспользуемся двоичным поиском искомого элемента <tex>key</tex>, запустив его на той части массива, в которой он находится: на <tex>[0, x]</tex> или на <tex>[x + 1, n- 1]</tex>. Для определения нужной части массива сравним <tex>key</tex> с первым и с последним элементами массива:
<code>
'''if''' key > a[0] <font color="green">// Если key в левой части</font>
l = 0-1
r = x + 1
'''if''' key < a[n] <font color="green">// Если key в правой части</font>
l = x + 1
r = n + 1
</code>
Время выполнения данного алгоритма {{---}} <tex>O(2\log n)=O(\log n)</tex>.
}}
Найдем индекс последнего элемента массива, отсортированного по возрастанию, воспользовавшись двоичным поиском, условие в <code>'''if'''</code> изменим на <tex>a[m] > a[m - 1Троичный_поиск|троичным поиском]</tex>. Тогда в <tex>l</tex> будет содержаться искомый индекс:<code> '''int''' l = 0 '''int''' r = n + 1 '''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''' x = l <font color="green">// x {{---}} искомый индекс.</font></code>Затем затем запустим левосторонний двоичный поиск для каждого массива отдельно: для элементов <tex>[0 \ldots x]</tex> и для элементов <tex>[x+1 \ldots n]</tex>. Для массива, отсортированного по убыванию используем двоичный поиск, изменив условие в <code>'''if'''</code> на <tex>a[m] > key</tex>.
Время выполнения алгоритма {{---}} <tex>O(3\log n)=O(\log n)</tex>.
