Изменения

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

Для простоты дальнейших определений будем считать, что <tex>a[0-1] = -\infty</tex> и что <tex>a[n+1] = +\infty</tex> (массив нумеруется с <tex>10</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> {{---}} искомый ключ}}

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

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

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

'''int''' l = 0 -1 <font color="green">// l, r {{---}} левая и правая границы</font> '''int''' r = len(a) + 1

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

'''int''' l = 0-1 '''int''' r = n + 1 len(a)

Затем воспользуемся двоичным поиском искомого элемента <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

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

Время выполнения алгоритма {{---}} <tex>O(3\log n)=O(\log n)</tex>(так как и бинарный поиск, и тернарный поиск работают за логарифмическое время с точностью до константы).

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

Для тогоДокажем, что найти этот индекс невозможно быстрее, чтобы чем за <tex>O\Omega (n)</tex> найти элемент . Возьмем возрастающий массив целых чисел, начиная с <tex>1</tex>. Он удовлетворяет условию задачи. Вставим в массивенего <tex>0</tex> на любую позицию. Такой массив по-прежнему будет удовлетворять условию задачи. Следовательно, нужно пройти по всем элементам массива и сравнить их с искомымиз-за того, что <tex>0</tex> может находиться на любой позиции, быстрее мы можем его найти элемент в таком массиве нельзялишь за <tex>\Omega (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[m] > a[m - 1]</tex> (ответ будет записан в <tex>l</tex>) или на <tex>a[m] > a[m + 1]</tex> (ответ будет записан в <tex>r</tex>) соответственно. Фактически, при поиске индексов минимума и максимума мы проверяем, возрастает или убывает массив на промежутке <tex> [ m - 1 ; m ] </tex>, а затем, в зависимости от того, что мы ищем, мы либо поднимаемся, либо опускаемся по этому промежутку возрастания (убывания). Однако при таком решении могут быть неправильно найдены значения минимума или максимума. Рассмотрим случаи, когда они будут неправильно найдены. Определить, какого вида наш массив возможно, сравнив первые два элемента массива.

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

В случае же убывание-возрастание-убывание (<tex> \searrow \nearrow \searrow </tex>) мы может быть, что будет неправильно найдем найден минимум. Найдем правильный минимум аналогично поиску максимума в предыдущем абзаце.

Затем, в зависимости от расположения частей (можно узнать, сравнив <tex>min</tex> и <tex>max</tex>)типа нашего массива, запустим двоичный бинарный поиск для каждой части отдельно аналогично задаче о поиске элемента три раза на массиве, отсортированном по возрастанию, в конец которого приписан массив, отсортированный по убываниюкаждом промежутке.

* [http://habrahabr.ru/post/146228/| Интересная статья про типичные Типичные ошибкипри написании бинарного поиска]* [http://algolist.manual.ru/search/advbin.php| Бинарный поиск на algolist] == Примечания ==<references/>