Изменения

Перейти к: навигация, поиск

Целочисленный двоичный поиск

492 байта убрано, 00:25, 4 октября 2019
Нет описания правки
'''Целочисленный двоичный поиск (бинарный поиск)''' (англ. <i>binary search</i>) {{---}} алгоритм поиска объекта по заданному признаку в множестве объектов, упорядоченных по тому же самому признаку, работающий за логарифмическое время.
{{Задача
|definition = Пусть нам дан упорядоченный массив, состоящий только из целочисленных элементов. Требуется найти позицию, на которой находится заданный элемент.
}}
[[Файл: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> {{---}} искомый ключ}}
{{Определение|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>[l,r]</tex> таких, что <tex>\forall i \in [l,r] : a[i] = x</tex> и <tex> \forall i \notin [l,r] : a[i] \neq x </tex>
<b><i>Например===Пример:</i></b>===
Задан отсортированный массив <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>.
Если искомого элемента в массиве нет, то правосторонний поиск выдаст минимальный элемент, больший искомого, а левосторонний наоборот, максимальный элемент, меньший искомого.
Идея поиска заключается в том, чтобы брать элемент посередине, между границами, и сравнивать его с искомым.
Если искомое больше(в случае правостороннего {{---}} не меньше), чем элемент сравнения,
то сужаем область поиска так, чтобы новая левая граница была равна индексу середины предыдущей области. В противном случае присваиваем это значение правой границе. Проделываем эту процедуру до тех пор, пока правая граница больше левой более чем на <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>
m = (l + r) / 2 <font color="green">// m {{---}} середина области поиска</font>
'''if''' a[m] < key
l = m
'''else'''
r = m <font color="green">// сужение Сужение границ</font>
'''return''' r
Заметим, что все элементы, которые лежат не правее <tex>startL</tex>, строго меньше текущего искомого элемента, так как они меньше предыдущего запроса, а значит и меньше текущего. Значит инвариант цикла выполнен.
== Применение двоичного поиска на некоторых неотсортированных массивах ====='''Применение поиска на циклически сдвинутом отсортированном массиве'''===
{{Задача|definition = Пусть отсортированный по возрастанию массив из <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-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>
l = m
'''else'''
'''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>.
==='''Применение поиска на массиве, отсортированном по возрастанию, в конец которого приписан массив, отсортированный по убыванию'''===
Найдем индекс последнего элемента {{Задача|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..\ldots x]</tex> и для элементов <tex>[x+1..\ldots n]</tex>, где в качестве <tex>x</tex> мы возьмем индекс максимума, найденный троичным поиском. Для массива, отсортированного по убыванию используем двоичный поиск, измененнив изменив условие в <texcode>'''if'''</texcode> на <tex>a[m] > key</tex>. Время выполнения алгоритма {{---}} <tex> O(\log n)</tex> (так как и бинарный поиск, и тернарный поиск работают за логарифмическое время с точностью до константы). 
Время выполнения алгоритма {{---Задача|definition = Два отсортированных по возрастанию массива записаны один в конец другого. Требуется максимально быстро найти элемент в таком массиве.}} <tex>O(3\log n)=O(\log n)</tex>.
Мы имеем массив, образованный из двух отсортированных подмассивов, записанных один в конец другого. Запустить сразу бинарный или тернарный поиски на таком массиве нельзя, так как массив не будет обязательно отсортированным и он не будет иметь <tex>1</tex> точку экстремума. Поэтому попробуем найти индекс последнего элемента левого массива, чтобы потом запустить бинарный поиск два раза на отсортированных массивах.
==='''Применение поиска Докажем, что найти этот индекс невозможно быстрее, чем за <tex>\Omega (n)</tex>. Возьмем возрастающий массив целых чисел, начиная с <tex>1</tex>. Он удовлетворяет условию задачи. Вставим в него <tex>0</tex> на двух отсортированных любую позицию. Такой массив по возрастанию массивах-прежнему будет удовлетворять условию задачи. Следовательно, из-за того, что <tex>0</tex> может находиться на любой позиции, записанных один в конец другого'''===мы можем его найти лишь за <tex>\Omega (n)</tex>.
Найдем индекс последнего элемента левого массива, заменив условие в <tex>if</tex> на <tex>a[m] < a[m-1]</tex>. Так мы найдем единственный элемент в массиве, который меньше предыдущего элемента (все остальные элементы больше предыдущего, так как массивы отсортированы по возрастанию). Однако такой алгоритм не будет работать, если левый массив длиннее, чем правый, и <tex>last</tex> будет равняться начальному значению <tex>l</tex>. Поэтому будем запускать такой алгоритм рекурсивно, если <tex>last</tex> равно начальному значению <tex>l</tex>, беря за новое начальное значение <tex>l</tex> середину массива. Таким образом мы запустим бинарный поиск еще <tex>O(\log n)</tex> раз, постоянно уменьшая массив в два раза. Тогда через <tex>O(\log n)</tex> итераций либо левый массив перестанет быть длиннее, чем правый, и значение <tex>last</tex> окажется отличным от <tex>a</tex> (начальное значение <tex>l</tex>), либо длина массива станет равной двум и рекурсия потеряет всякий смысл (если в таком случае <tex>last</tex> останется равным <tex>a</tex>, то, значит, что первый элемент правого массива больше последнего элемента левого массива. Тогда два массива будут являться одним массивом отсортированным по возрастанию). После выполнения этого алгоритма <tex>last</tex> и будет номером последнего элемента из левого массива.
<code>{{Задача <font color|definition ="green">// Поиск последнего элемента левого Массив образован путем циклического сдвига массива</font> '''int''' a = 0 '''int''' b = n + 1 '''function''' indexOfLastLeftArrayElement('''int''' a,'''int''' b) '''int''' l = a '''int''' r = b '''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''' last = l '''if''' last == a '''and''' r - (a + b) / 2 > 1 indexOfLastLeftArrayElement((a + b) / 2, r)</code>
Проверим, равен ли После циклического сдвига мы получим массив <tex>lasta[0 \ldots n-1]</tex> , образованный из трех частей: отсортированных по возрастанию-убыванию-возрастанию (<tex>a\nearrow \searrow \nearrow </tex>. Если да, то запустим бинарный поиск на массиве от ) или по убыванию-возрастанию-убыванию (<tex>0\searrow \nearrow \searrow </tex> до ). С помощью двоичного поиска найдем индексы максимального и минимального элементов массива, заменив условие в <texcode>n'''if'''</texcode>. Иначе, зная номер последнего элемента левого массива, запустим два раза левосторонний бинарный поиск: на массиве от <tex>0a[m] > a[m - 1]</tex> до (ответ будет записан в <tex>lastl</tex>, и ) или на массиве от <tex>last a[m] > a[m + 1]</tex> до (ответ будет записан в <tex>nr</tex>) соответственно.
Время выполнения алгоритма {{---}} Фактически, при поиске индексов минимума и максимума мы проверяем, возрастает или убывает массив на промежутке <tex>O(\log^2 n)[ m - 1 ; m ] </tex> (, а затем, в зависимости от того, что мы ищем, мы запускаем бинарный поисклибо поднимаемся, который требует <tex>Oлибо опускаемся по этому промежутку возрастания (\log n)</tex> времени <tex>O(\log n)</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/>
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы поиска]]
Анонимный участник

Навигация