Изменения
→Код
'''Целочисленный двоичный поиск (бинарный поиск)''' (англ. <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>
Задан отсортированный массив <tex>[1, 2, 2, 2, 2, 3, 5, 8, 9, 11], x = 2</tex>.
Правосторонний поиск двойки выдаст в результате <tex>54</tex>, в то время как левосторонний выдаст <tex>21</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>m</tex> присваевается левой границе <tex>l</tex>, только тогда, когда <tex>a[m]</tex> строго меньше искомого элемента <tex>key</tex>), тогда если <tex>r = l + 1</tex> (что эквивалентно <tex>r-l=1</tex>), то понятно, что <tex>r</tex> {{---}} самое левое вхождение искомого элемента (так как предыдущие элементы уже меньше искомого элемента)
В случае правостороннего поиска изменится знак сравнения при сужении границ на <tex>a[m] \leqslant k</tex>.
== Несколько слов об эвристиках ==
Заметим, что все элементы, которые лежат не правее <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>[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>1</tex> точку экстремума. Поэтому попробуем найти индекс последнего элемента левого массива, чтобы потом запустить бинарный поиск два раза на отсортированных массивах.
Рассмотрим отдельно ситуацию, если наш массив вида возрастание-убывание-возрастание (<tex>\nearrow \searrow \nearrow </tex>). В таком случае может быть неправильно найдено значение максимума, если последний промежуток возрастания занимает больше половины массива (мы будем подниматься по последнему промежутку возрастания вплоть до конца массива и за максимум будет принят последний элемент массива, что не всегда верно). Тогда, если последний элемент массива меньше первого, нужно еще раз запустить поиск максимума, но уже на промежутке от <tex>0</tex> до <tex>min</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 Википедия {{--- }} двоичный поиск]* [http://habrahabr.ru/post/146228/| Интересная статья про типичные Типичные ошибкипри написании бинарного поиска]* [http://algolist.manual.ru/search/advbin.php| Бинарный поиск на algolist] == Примечания ==<references/>
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы поиска]]