65
правок
Изменения
Исправлена часть про бинарный поиск на неотсортированных массивах
Заметим, что все элементы, которые лежат не правее <tex>startL</tex>, строго меньше текущего искомого элемента, так как они меньше предыдущего запроса, а значит и меньше текущего. Значит инвариант цикла выполнен.
== Применение двоичного поиска на некоторых неотсортированных массивах ==
==='''Применение поиска на циклически сдвинутом отсортированном массиве'''===
Пусть отсортированный по возрастанию массив из <tex>n</tex> элементов <tex>a[0..\ldots n- 1]</tex>, все элементы которого различны, был циклически сдвинут, тогда полученный массив состоит из двух отсортированных частей. Используем двоичный поиск, чтобы найти индекс последнего элемента левой части массива. Для этого в реализации двоичного поиска заменим условие в <texcode>'''if'''</texcode> на <tex>a[m] > a[n-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[n- 1] <font color="green">// Сужение границ..</font>
l = m
'''else'''
Затем воспользуемся двоичным поиском искомого элемента <tex>key</tex>, запустив его на той части массива, в которой он находится: на <tex>[0, x]</tex> или на <tex>[x + 1, n]</tex>. Для определения нужной части массива сравним <tex>key</tex> с первым и с последним элементами массива:
<code>
'''if''' key > a[0] <font color="green">// Если key в левой части...</font>
l = 0
r = x + 1
'''if''' key < a[n] <font color="green">// Если key в правой части...</font>
l = x + 1
r = n + 1
==='''Применение поиска на массиве, отсортированном по возрастанию, в конец которого приписан массив, отсортированный по убыванию'''===
Найдем индекс последнего элемента массива, отсортированного по возрастанию, воспользовавшись двоичным поиском, условие в <texcode>'''if'''</texcode> в котором изменено изменим на <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'''
'''int''' x = l <font color="green">// x {{---}} искомый индекс.</font>
</code>
Затем запустим левосторонний двоичный поиск для каждого массива отдельно: для элементов <tex>[0..\ldots x]</tex> и для элементов <tex>[x+1..\ldots n]</tex>. Для массива, отсортированного по убыванию используем двоичный поиск, измененнив изменив условие в <texcode>'''if'''</texcode> на <tex>a[m] > key</tex>.
Время выполнения алгоритма {{---}} <tex>O(3\log n)=O(\log n)</tex>.
# <tex> \{ 1,2,3 \mid 4,5,6 \}</tex> {{---}} все элементы из второго массива больше последнего (максимального) элемента из первого массива. Стоит заметить, что массив в этом примере не отличим от массивов: <tex>\{ 1 \mid 2,3,4,5,6 \}</tex>, <tex>\{ 1,2 \mid 3,4,5,6 \}</tex> и тому подобных.
Запустить сразу бинарный поиск на таком массиве (образованном из двух маленьких) не представляется разумным, так как массив не будет обязательно отсортированным. Также нельзя запустить другие поиски, работающие за <tex>O( \log n)</tex>, так как точек экстремума несколько, и нет никакой дополнительной информации об элементах в массивах. Поэтому попробуем найти индекс последнего элемента левого массива, чтобы потом запустить бинарный поиск два раза на отсортированных массивах. Найти последний элемент левого массива с помощью алгоритмов поиска, которые ищут максимум на массиве тоже не представляется возможнымневозможно, потому что элементы правого массива (все или некоторые) могут быть больше последнего элемента левого массива.
Для того, чтобы за <tex>O(n)</tex> найти элемент в массиве пройти по всем элементам массива и сравнить их с искомым.
==='''Применение поиска на циклически сдвинутом массиве, образованном приписыванием отсортированного по убыванию массива в конец отсортированного по возрастанию'''===
После циклического сдвига мы получим массив <tex>a[0..\ldots n-1]</tex>, образованный из трех частей: отсортированных по возрастанию-убыванию-возрастанию или по убыванию-возрастанию-убыванию. Поэтому с помощью двоичного поиска мы ищем индексы максимального и минимального элементов массива, заменив условие в <texcode>'''if'''</texcode> на <tex>a[m] > a[m - 1]</tex> (ответ будет записан в <tex>l</tex>) или на <tex>a[m] > a[m + 1]</tex> (ответ будет записан в <tex>r</tex>) соответственно:
<code>
<font color="green">// Поиск максимума...</font>
'''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'''
'''int''' max = l
<font color="green">// Поиск минимума...</font>
'''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'''
'''int''' min = r
</code>
Рассмотрим отдельно ситуацию, если наш массив вида возрастание-убывание-возрастание. В таком случае будет неправильно найдено значение максимума (<tex>max</tex>), если длина последнего промежутка возрастания больше или равна половине всего массива. В <tex>r</tex> будет храниться изначальное значение, то есть <tex>n+1</tex>. Тогда нужно сравнить последний элемент массива с первым элементом, и, если первый элемент больше последнего, запустить еще раз бинарный поиск для поиска максимума с таким же условием, но уже с начальными значениями <tex>l=0</tex>, <tex>r=min</tex>. За значение максимума принять новое значение. Если последний элемент окажется больше первого, за значение максимума принять значение последнего элемента.
Теперь рассмотрим ситуацию, когда наш массив вида убывание-возрастание-убывание. Тогда будет неправильно найдено значение минимума (<tex>min</tex>), если длина первого промежутка убывания больше или равна половине всего массива. В <tex>r</tex> будет храниться изначальное значение, то есть <tex>n+1</tex>. Тогда нужно сравнить последний элемент массива с первым элементом, и, если первый элемент меньше последнего, запустить еще раз бинарный поиск для поиска минимума с таким же условием, но уже с начальными значениями <tex>l=0</tex>, <tex>r=max</tex>. За значение минимума принять новое значение. Если последний элемент окажется меньше первого, за значение минимума принять значение последнего элемента.
Затем, в зависимости от расположения частей (можно узнать, сравнив <tex>min</tex> и <tex>max</tex>), запустим двоичный поиск для каждой части отдельно аналогично задаче о поиске элемента на массиве, отсортированном по возрастанию, в конец которого приписан массив, отсортированный по убыванию.
Время выполнения данного алгоритма {{---}} <tex>O(56\log n)=O(\log n)</tex>.
== См. также ==
