Изменения

Для простоты дальнейших определений будем считать, что <tex>a[0] = -\infty</tex> и что <tex>a[n+1] = +\infty</tex>(массив нумеруется с <tex>1</tex>).

<b><i>Например===Пример:</i></b>===

'''int''' binSearch('''int[]''' a, '''int''' key) : <font color="green">// l, r - левая и правая границыЗапускаем бинарный поиск</font> '''int''' l = 0 <font color="green">// l, r {{---}} левая и правая границы</font>

'''while''' l < r - 1 <font color="green">// запускаем Запускаем цикл</font>

r = m <font color="green">// сужение Сужение границ</font>

{{Задача|definition = Пусть отсортированный по возрастанию массив из <tex>n</tex> элементов <tex>a[0 \ldots n - 1]</tex>, все элементы которого различны, был циклически сдвинут, требуется максимально быстро найти элемент в таком массиве.}} Если массив, отсортированный по возрастанию, был циклически сдвнут, тогда полученный массив состоит из двух отсортированных частей. Используем двоичный поиск, чтобы найти индекс последнего элемента левой части массива. Для этого в реализации двоичного поиска заменим условие в <code>'''if'''</code> на <tex>a[m] > a[n-1]</tex>, тогда в <tex>l</tex> будет содержаться искомый индекс:

'''while''' l < r - 1 <font color="green">// Запускаем циклС помощью бинарного поиска найдем максимум на массиве</font>

 {{Задача|definition ==='''Применение поиска на массивеМассив образован путем приписывания в конец массива, отсортированном отсортированного по возрастанию, в конец которого приписан массивмассива, отсортированный отсортированного по убыванию'''===. Требуется максимально быстро найти элемент в таком массиве.}}

'''while''' l < r - 1 <font color="green">// Запускаем циклС помощью бинарного поиска найдем точку экстремума на массиве</font>

{{Задача|definition ==='''Применение поиска на двух Два отсортированных по возрастанию массивах, записанных массива записаны один в конец другого'''===. Требуется максимально быстро найти элемент в таком массиве.}}

Мы имеем массив, образованный из двух отсортированных массивовподмассивов, записанных один в конец другого. Рассмотрим разные примеры таких массивов (вертикальная черта означает границу между двумя маленькими массивами, образующими большойзапустить сразу бинарный поиск на таком массиве нельзя, никакой смысловой нагрузки она так как массив не несетбудет обязательно отсортированным. Также нельзя запустить другие поиски, она нужна лишь для облегчения понимания):# работающие за <tex> O( \{ 1, 3, 5 \mid 2, 4, 6 \}log n)</tex> или <tex> \{ 2, 4так как неизвестно количество точек экстремума, 6 \mid 1, 3, 5 \}</tex> {{---}} самые частые вариантыи нет никакой дополнительной информации об элементах в массивах.# <tex> \{ 100 \mid 1 \}</tex> {{---}} оба Поэтому попробуем найти индекс последнего элемента левого массива имеют длину <tex>1</tex>, чтобы потом запустить бинарный поиск два раза на отсортированных массивах.# Рассмотрим массивы <tex> \{ 1,2,3 \mid 4,5,6 \}</tex> {{---}} все элементы из второго массива больше последнего (максимального) элемента из первого массива. Стоит заметить, что массив в этом примере не отличим от массивов: и <tex>\{ 1 \mid ,2,3, 4,5\mid \textbf{0} ,6 \}</tex>(вертикальная черта означает границу между левым и правым массивами): все элементы, <tex>\{ 1кроме пятого не меняются, значит,2 \mid 3по другим элементам невозможно определить,4есть ли в правом массиве элемент,5который меньше элементов левого массива,6 \}поэтому для нахождения конца левого массива придется сравнить все элементы с соседними за <tex>O(n)</tex> и тому подобных, тогда проще сразу искать нужный элемент, а не конец левого массива.

Запустить сразу бинарный поиск на таком массиве (образованном из двух маленьких) не представляется разумнымДля того, так как массив не будет обязательно отсортированным. Также нельзя запустить другие поиски, работающие чтобы за <tex>O( \log n)</tex>, так как точек экстремума несколько, и нет никакой дополнительной информации об элементах найти элемент в массивах. Поэтому попробуем найти индекс последнего элемента левого массивамассиве, чтобы потом запустить бинарный поиск два раза на отсортированных массивах. Найти последний элемент левого нужно пройти по всем элементам массива и сравнить их с помощью алгоритмов поискаискомым, которые ищут максимум на быстрее найти элемент в таком массиве тоже невозможно, потому что элементы правого массива (все или некоторые) могут быть больше последнего элемента левого массиванельзя.

Для того{{Задача|definition = Массив образован путем циклического сдвига массива, чтобы за <tex>O(n)</tex> образованного приписыванием отсортированного по убыванию массива в конец отсортированного по возрастанию . Требуется максимально быстро найти элемент в таком массиве пройти по всем элементам массива и сравнить их с искомым.}}

==='''Применение поиска на циклически сдвинутом массивеРассмотрим отдельно ситуацию, образованном приписыванием отсортированного по убыванию массива в конец отсортированного по возрастанию'''=== После циклического сдвига мы получим если наш массив <tex>a[0 \ldots nвида возрастание-1]</tex>, образованный из трех частей: отсортированных по возрастаниюубывание-убыванию-возрастанию или по убыванию-возрастанию-убыванию. Поэтому с помощью двоичного поиска мы ищем индексы максимального и минимального элементов массива, заменив условие в <code>'''if'''</code> на <tex>a[m] > a[m - 1]</tex> возрастание (ответ будет записан в <tex>l</tex>) или на <tex>a[m] > a[m + 1]</tex> (ответ будет записан в <tex>r\nearrow \searrow \nearrow </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''' r = m '''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''' r = m '''int''' min = r</code> Рассмотрим отдельно ситуацию, если наш массив вида возрастание-убывание-возрастание. В таком случае будет может быть неправильно найдено значение максимума (<tex>max</tex>), если длина последнего промежутка возрастания больше или равна половине всего массива. В <tex>r</tex> будет храниться изначальное значение, то есть <tex>n+1</tex>. Тогда нужно сравнить если последний элемент массива с первым элементомменьше первого, и, если первый элемент больше последнего, запустить нужно еще раз бинарный запустить поиск для поиска максимума с таким же условием, но уже с начальными значениями на промежутке от <tex>l=0</tex>, до <tex>r=min</tex>. За значение максимума принять новое значение. Если последний элемент окажется больше первого, за значение максимума принять значение последнего элемента.

Теперь рассмотрим ситуацию, когда наш массив вида В случае же убывание-возрастание-убывание. Тогда будет неправильно найдено значение минимума (<tex>min\searrow \nearrow \searrow </tex>), если длина первого промежутка убывания больше или равна половине всего массива. В <tex>r</tex> будет храниться изначальное значение, то есть <tex>n+1</tex>. Тогда нужно сравнить последний элемент массива с первым элементом, и, если первый элемент меньше последнего, запустить еще раз бинарный поиск для поиска минимума с таким же условием, но уже с начальными значениями <tex>l=0</tex>, <tex>r=max</tex>. За значение минимума принять новое значениемы неправильно найдем минимум. Если последний элемент окажется меньше первого, за значение минимума принять значение последнего элементаНайдем правильный минимум аналогично поиску максимума в предыдущем абзаце.

* Д. Кнут {{- --}} Искусство программирования (Том 3, 2-е издание)* [http://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA Википедия {{--- }} двоичный поиск]