Изменения

[[Файл:shcemebinsearch.png|350px320px|thumb|right|Схема бинарного поиска]] == Формулировка задачи ==Пусть нам дан упорядоченный массив, состоящий только из целочисленных элементов. Требуется найти позицию, на которой находится заданный элемент. Для этой задачи мы и можем использовать двоичный поиск.

Для простоты дальнейших определений будем считать, что <tex>a[0-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> {{---}} искомый ключ}}

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

Правосторонний поиск двойки выдаст в результате <tex>54</tex>, в то время как левосторонний выдаст <tex>21</tex> (нумерация с единицынуля).

От сюда Отсюда следует, что количество подряд идущих двоек равно длине отрезка <tex>[21;54]</tex>, то есть <tex>4</tex>.

Если искомого элемента в массиве нет, то правосторонний поиск выдаст минимальный максимальный элемент, больший меньший искомого, а левосторонний наоборот, максимальный минимальный элемент, меньший больший искомого.

то сужаем область поиска так, чтобы новая левая граница была равна индексу середины предыдущей области. В противном случае присваиваем это значение правой границе. Проделываем эту процедуру до тех пор, пока правая граница больше левой более чем на <tex>1</tex>. В случае правостороннего бинарного поиска ответом будет индекс <tex>l</tex>, а в случае левостороннего {{---}} <tex>r</tex>.

'''int''' binSearch('''int[]''' a, '''int''' key) : <font color="green">// l, r - левая и правая границыЗапускаем бинарный поиск</font> '''int''' l = 0-1 <font color="green">// l, r {{---}} левая и правая границы</font> '''int''' r = len(a) + 1 '''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>, все элементы которого различны, был циклически сдвинутом отсортированном сдвинут, требуется максимально быстро найти элемент в таком массиве'''===.}}

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

'''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> '''if''' a[m] < > a[n- 1] <font color="green">// Сужение границ..</font>

Затем воспользуемся двоичным поиском искомого элемента <tex>key</tex>, запустив его на той части массива, в которой он находится: на <tex>[0, x]</tex> или на <tex>[x + 1, n- 1]</tex>. Для определения нужной части массива сравним <tex>key</tex> с первым и с последним элементами массива:

'''if''' key > a[0] <font color="green">// Если key в левой части...</font> l = 0-1

'''if''' key < a[n] <font color="green">// Если key в правой части...</font> l = x + 1 r = n + 1

Время выполнения данного алгоритма {{---}} <tex>O(2\log n)=O(\log n)</tex>.  {{Задача|definition = Массив образован путем приписывания в конец массива, отсортированного по возрастанию, массива, отсортированного по убыванию. Требуется максимально быстро найти элемент в таком массиве.}} Найдем индекс последнего элемента массива, отсортированного по возрастанию, воспользовавшись [[Троичный_поиск|троичным поиском]], затем запустим левосторонний двоичный поиск для каждого массива отдельно: для элементов <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> (так как и бинарный поиск, и тернарный поиск работают за логарифмическое время с точностью до константы). 

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

Найдем индекс последнего элемента массива, отсортированного по возрастаниюМы имеем массив, воспользовавшись двоичным поискомобразованный из двух отсортированных подмассивов, условие записанных один в <tex>if</tex> в котором изменено конец другого. Запустить сразу бинарный или тернарный поиски на <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..x]</tex> обязательно отсортированным и для элементов он не будет иметь <tex>[x+1..n]</tex>точку экстремума. Для Поэтому попробуем найти индекс последнего элемента левого массива, отсортированного по убыванию используем двоичный чтобы потом запустить бинарный поиск, измененнив условие в <tex>if</tex> два раза на <tex>a[m] > key</tex>отсортированных массивах.

Время выполнения алгоритма {{Докажем, что найти этот индекс невозможно быстрее, чем за <tex>\Omega (n)</tex>. Возьмем возрастающий массив целых чисел, начиная с <tex>1</tex>. Он удовлетворяет условию задачи. Вставим в него <tex>0</tex> на любую позицию. Такой массив по-прежнему будет удовлетворять условию задачи. Следовательно, из--}} за того, что <tex>0</tex> может находиться на любой позиции, мы можем его найти лишь за <tex>O\Omega (3\log n)</tex>.

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

Индекс последнего элемента левого После циклического сдвига мы получим массив <tex>a[0 \ldots n-1]</tex>, образованный из трех частей: отсортированных по возрастанию-убыванию-возрастанию (<tex>\nearrow \searrow \nearrow </tex>) или по убыванию-возрастанию-убыванию (<tex> \searrow \nearrow \searrow </tex>). С помощью двоичного поиска найдем индексы максимального и минимального элементов массива найдем так же, как заменив условие в предыдущей задаче. Затем запустим двоичный поиск для каждого массива отдельно: для <code>'''if'''</code> на <tex>a[0..xm] > a[m - 1]</tex> и для (ответ будет записан в <tex>l</tex>) или на <tex>a[xm] > a[m +1..n]</tex>(ответ будет записан в <tex>r</tex>) соответственно.

Время выполнения алгоритма {{---}} Фактически, при поиске индексов минимума и максимума мы проверяем, возрастает или убывает массив на промежутке <tex>O(3\log n)[ m - 1 ; m ] </tex>, а затем, в зависимости от того, что мы ищем, мы либо поднимаемся, либо опускаемся по этому промежутку возрастания (убывания). Однако при таком решении могут быть неправильно найдены значения минимума или максимума. Рассмотрим случаи, когда они будут неправильно найдены. Определить, какого вида наш массив возможно, сравнив первые два элемента массива.

==='''Применение поиска на циклически сдвинутом массивеРассмотрим отдельно ситуацию, если наш массив вида возрастание-убывание-возрастание (<tex>\nearrow \searrow \nearrow </tex>). В таком случае может быть неправильно найдено значение максимума, образованном приписыванием отсортированного если последний промежуток возрастания занимает больше половины массива (мы будем подниматься по убыванию последнему промежутку возрастания вплоть до конца массива и за максимум будет принят последний элемент массива, что не всегда верно). Тогда, если последний элемент массива меньше первого, нужно еще раз запустить поиск максимума, но уже на промежутке от <tex>0</tex> до <tex>min</tex>, потому что истинный максимум будет находиться в конец отсортированного по возрастанию'''===первой точке экстремума, которую мы таким образом и найдем.

После циклического сдвига мы получим массив <tex>a[0..n]</tex>, образованный из трех частей: отсортированных по возрастанию-убыванию-возрастанию или по убываниюВ случае же убывание-возрастаниювозрастание-убыванию. Поэтому с помощью двоичного поиска мы ищем индексы максимального и минимального элементов массива, заменив условие в <tex>if</tex> на <tex>a[m] > a[m - 1]</tex> убывание (ответ будет записан в <tex>l\searrow \nearrow \searrow </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''' 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 Время выполнения данного алгоритма {{---}} середина области поиска.</fonttex> '''if''' a[m] > a[m + 1] <font color="green">// Сужение границ..</font> l = m '''else''' r = m '''int''' min O(6\log n)= r</code>Затем, в зависимости от расположения частей O(можно узнать, сравнив <tex>min\log n)</tex> и <tex>max</tex>), запустим двоичный поиск для каждой части отдельно аналогично задаче о поиске элемента на массиве, отсортированном по возрастанию, в конец которого приписан массив, отсортированный по убыванию.

Время выполнения данного алгоритма {{---}} == Переполнение индекса середины ==В некоторых языках программирования присвоение <code>m = (l + r) / 2</code> приводит к переполнению. Вместо этого рекомендуется использовать <texcode>Om = l + (5\log nr - l)/ 2;</texcode>или эквивалентные выражения.<ref>https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html</ref>

* Д. Кнут {{- --}} Искусство программирования (Том 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 Википедия {{--- }} двоичный поиск]* [http://habrahabr.ru/post/146228/| Интересная статья про типичные Типичные ошибкипри написании бинарного поиска]* [http://algolist.manual.ru/search/advbin.php| Бинарный поиск на algolist] == Примечания ==<references/>