Изменения

[[Файл: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>, все элементы которого различны, был циклически сдвинут, требуется максимально быстро найти элемент в таком массиве.}} Если массив, отсортированный по возрастанию, был циклически сдвинут, тогда полученный массив состоит из двух отсортированных частей. Используем двоичный поиск, чтобы найти индекс последнего элемента левой части массива. Для этого в реализации двоичного поиска заменим условие в <code>'''if'''</code> на <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>

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

l = 0-1

l = x + 1 r = n + 1

Найдем индекс последнего элемента {{Задача|definition = Массив образован путем приписывания в конец массива, отсортированного по возрастанию, воспользовавшись двоичным поиском, условие в <code>'''if'''</code> изменим на <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>. Для массива, отсортированного по убыванию используем двоичный поиск, изменив условие . Требуется максимально быстро найти элемент в <code>'''if'''</code> на <tex>a[m] > key</tex>таком массиве.}}

Время выполнения алгоритма {{---}} Найдем индекс последнего элемента массива, отсортированного по возрастанию, воспользовавшись [[Троичный_поиск|троичным поиском]], затем запустим левосторонний двоичный поиск для каждого массива отдельно: для элементов <tex>O(3[0 \log n)=O(ldots x]</tex> и для элементов <tex>[x+1 \log ldots n)]</tex>, где в качестве <tex>x</tex> мы возьмем индекс максимума, найденный троичным поиском. Для массива, отсортированного по убыванию используем двоичный поиск, изменив условие в <code>'''if'''</code> на <tex>a[m] > key</tex>.

Мы имеем массив, образованный из двух {{Задача|definition = Два отсортированных массивов, записанных по возрастанию массива записаны один в конец другого. Рассмотрим разные примеры таких массивов (вертикальная черта означает границу между двумя маленькими массивами, образующими большой, никакой смысловой нагрузки она не несет, она нужна лишь для облегчения понимания):# <tex> \{ 1, 3, 5 \mid 2, 4, 6 \}</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,6 \}</tex>, <tex>\{ 1,2 \mid 3,4,5,6 \}</tex> и тому подобных.

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

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

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

<font color="green">// Поиск Фактически, при поиске индексов минимумаи максимума мы проверяем, возрастает или убывает массив на промежутке </fonttex> '''int''' l = 0 '''int''' r = n + 1 '''while''' l < r [ m - 1 ; m ] <font color="green">// Запускаем цикл</fonttex> 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\nearrow \searrow \nearrow </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>. За значение минимума принять новое значение. Если последний элемент окажется меньше первого, за значение минимума принять значение последнего элементаНайдем правильный минимум аналогично поиску максимума в предыдущем абзаце.

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