Целочисленный двоичный поиск — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (изменен алгоритм 7.2)
м (rollbackEdits.php mass rollback)
 
(не показано 18 промежуточных версий 8 участников)
Строка 1: Строка 1:
 
'''Целочисленный двоичный поиск (бинарный поиск)''' (англ. <i>binary search</i>)  {{---}} алгоритм поиска объекта по заданному признаку в множестве объектов, упорядоченных по тому же самому признаку, работающий за логарифмическое время.  
 
'''Целочисленный двоичный поиск (бинарный поиск)''' (англ. <i>binary search</i>)  {{---}} алгоритм поиска объекта по заданному признаку в множестве объектов, упорядоченных по тому же самому признаку, работающий за логарифмическое время.  
 +
{{Задача
 +
|definition = Пусть нам дан упорядоченный массив, состоящий только из целочисленных элементов. Требуется найти позицию, на которой находится заданный элемент.
 +
}}
  
[[Файл:shcemebinsearch.png|350px|thumb|right|Схема бинарного поиска]]
+
[[Файл:shcemebinsearch.png|320px|thumb|right|Схема бинарного поиска]]
 
 
== Формулировка задачи ==
 
Пусть нам дан упорядоченный массив, состоящий только из целочисленных элементов. Требуется найти позицию, на которой находится заданный элемент. Для этой задачи мы и можем использовать двоичный поиск.
 
  
 
==Принцип работы==
 
==Принцип работы==
Строка 10: Строка 10:
  
 
== Правосторонний/левосторонний целочисленный двоичный поиск ==
 
== Правосторонний/левосторонний целочисленный двоичный поиск ==
Для простоты дальнейших определений будем считать, что <tex>a[0] = -\infty</tex> и что <tex>a[n] = +\infty</tex>.
+
Для простоты дальнейших определений будем считать, что <tex>a[-1] = -\infty</tex> и что <tex>a[n] = +\infty</tex> (массив нумеруется с <tex>0</tex>).
  
{{Определение|definition='''Правосторонний бинарный поиск''' (англ. <i>rightside binary search</i>) {{---}} бинарный поиск, с помощью которого мы ищем <tex> \max\limits_{i \in [0,n]} \{i  \mid  a[i] \leqslant x\} </tex>, где <tex>a</tex> {{---}} массив, а <tex>x</tex> {{---}} искомый ключ}}
+
{{Определение|definition='''Правосторонний бинарный поиск''' (англ. <i>rightside binary search</i>) {{---}} бинарный поиск, с помощью которого мы ищем <tex> \max\limits_{i \in [-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> {{---}} искомый ключ}}
 
{{Определение|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> {{---}} искомый ключ}}
Строка 18: Строка 18:
 
Использовав эти два вида двоичного поиска, мы можем найти отрезок позиций <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>[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>[1, 2, 2, 2, 2, 3, 5, 8, 9, 11], x = 2</tex>.
  
Правосторонний поиск двойки выдаст в результате <tex>5</tex>, в то время как левосторонний выдаст <tex>2</tex> (нумерация с единицы).
+
Правосторонний поиск двойки выдаст в результате <tex>4</tex>, в то время как левосторонний выдаст <tex>1</tex> (нумерация с нуля).
  
От сюда следует, что количество подряд идущих двоек равно длине отрезка <tex>[2;5]</tex>, то есть <tex>4</tex>.
+
Отсюда следует, что количество подряд идущих двоек равно длине отрезка <tex>[1;4]</tex>, то есть <tex>4</tex>.
  
Если искомого элемента в массиве нет, то правосторонний поиск выдаст минимальный элемент, больший искомого, а левосторонний наоборот, максимальный элемент, меньший искомого.
+
Если искомого элемента в массиве нет, то правосторонний поиск выдаст максимальный элемент, меньший искомого, а левосторонний наоборот, минимальный элемент, больший искомого.
  
 
== Алгоритм двоичного поиска ==  
 
== Алгоритм двоичного поиска ==  
 
Идея поиска заключается в том, чтобы брать элемент посередине, между границами, и сравнивать его с искомым.
 
Идея поиска заключается в том, чтобы брать элемент посередине, между границами, и сравнивать его с искомым.
 
Если искомое больше(в случае правостороннего {{---}} не меньше), чем элемент сравнения,
 
Если искомое больше(в случае правостороннего {{---}} не меньше), чем элемент сравнения,
то сужаем область поиска так, чтобы новая левая граница была равна индексу середины предыдущей области. В противном случае присваиваем это значение правой границе. Проделываем эту процедуру до тех пор, пока правая граница больше левой более чем на <tex>1</tex>. В случае правостороннего бинарного поиска ответом будет индекс <tex>l</tex>, а в случае левостороннего {{---}} <tex>r</tex>.  
+
то сужаем область поиска так, чтобы новая левая граница была равна индексу середины предыдущей области. В противном случае присваиваем это значение правой границе. Проделываем эту процедуру до тех пор, пока правая граница больше левой более чем на <tex>1</tex>.
  
 
== Код ==
 
== Код ==
  '''int''' binSearch('''int[]''' a, '''int''' key)   <font color="green">// l, r - левая и правая границы</font>
+
  '''int''' binSearch('''int[]''' a, '''int''' key)<font color="green">// Запускаем бинарный поиск</font>
     '''int''' l = 0
+
     '''int''' l = -1                      <font color="green">// l, r {{---}} левая и правая границы</font>
     '''int''' r = len(a) + 1    
+
     '''int''' r = len(a)     
     '''while''' l < r - 1                <font color="green">// запускаем цикл</font>
+
     '''while''' l < r - 1                <font color="green">// Запускаем цикл</font>
 
         m = (l + r) / 2            <font color="green">// m {{---}} середина области поиска</font>
 
         m = (l + r) / 2            <font color="green">// m {{---}} середина области поиска</font>
 
         '''if''' a[m] < key
 
         '''if''' a[m] < key
 
             l = m
 
             l = m
 
         '''else'''  
 
         '''else'''  
             r = m                  <font color="green">// сужение границ</font>
+
             r = m                  <font color="green">// Сужение границ</font>
 
     '''return''' r
 
     '''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>l = r - 1</tex>, то понятно, что <tex>l</tex> {{---}} самое правое вхождение (так как следующее уже больше).
+
В случае правостороннего поиска изменится знак сравнения при сужении границ на <tex>a[m] \leqslant k</tex>, а возвращаемой переменной станет <tex>l</tex>.
  
 
== Несколько слов об эвристиках ==
 
== Несколько слов об эвристиках ==
Строка 65: Строка 65:
 
Заметим, что все элементы, которые лежат не правее <tex>startL</tex>, строго меньше текущего искомого элемента, так как они меньше предыдущего запроса, а значит и меньше текущего. Значит инвариант цикла выполнен.   
 
Заметим, что все элементы, которые лежат не правее <tex>startL</tex>, строго меньше текущего искомого элемента, так как они меньше предыдущего запроса, а значит и меньше текущего. Значит инвариант цикла выполнен.   
  
== Применение двоичного поиска на неотсортированных массивах ==
+
== Применение двоичного поиска на некоторых неотсортированных массивах ==
==='''Применение поиска на циклически сдвинутом отсортированном массиве'''===
 
  
Пусть отсортированный по возрастанию массив <tex>a[0..n]</tex>, все элементы которого различны, был циклически сдвинут, тогда полученный массив состоит из двух отсортированных частей. Используем  двоичный поиск, чтобы найти индекс последнего элемента левой части массива. Для этого в реализации двоичного поиска заменим условие в <tex>if</tex> на <tex>a[m] > a[n]</tex>, тогда в <tex>l</tex> будет содержаться искомый индекс:
+
{{Задача
 +
|definition = Пусть отсортированный по возрастанию массив из <tex>n</tex> элементов <tex>a[0 \ldots n - 1]</tex>, все элементы которого различны, был циклически сдвинут, требуется максимально быстро найти элемент в таком массиве.
 +
}}
 +
 
 +
Если массив, отсортированный по возрастанию, был циклически сдвинут, тогда полученный массив состоит из двух отсортированных частей. Используем  двоичный поиск, чтобы найти индекс последнего элемента левой части массива. Для этого в реализации двоичного поиска заменим условие в <code>'''if'''</code> на <tex>a[m] > a[n-1]</tex>, тогда в <tex>l</tex> будет содержаться искомый индекс:
 
<code>
 
<code>
  '''int''' l = 0
+
  '''int''' l = -1
  '''int''' r = n + 1   
+
  '''int''' r = len(a) 
  '''while''' l < r - 1                <font color="green">// Запускаем цикл...</font>
+
  '''while''' l < r - 1                <font color="green">// С помощью бинарного поиска найдем максимум на массиве</font>
     m = (l + r) / 2            <font color="green">// m {{---}} середина области поиска.</font>
+
     m = (l + r) / 2            <font color="green">// m {{---}} середина области поиска</font>
     '''if''' a[m] > a[n]             <font color="green">// Сужение границ..</font>
+
     '''if''' a[m] > a[n - 1]         <font color="green">// Сужение границ</font>
 
         l = m
 
         l = m
 
     '''else'''  
 
     '''else'''  
Строка 80: Строка 83:
 
  '''int''' x = l                      <font color="green">// x {{---}} искомый индекс.</font>
 
  '''int''' x = l                      <font color="green">// x {{---}} искомый индекс.</font>
 
</code>
 
</code>
Затем воспользуемся двоичным поиском искомого элемента <tex>key</tex>, запустив его на той части массива, в которой он находится: на <tex>[0, x]</tex> или на <tex>[x + 1, n]</tex>. Для определения нужной части массива сравним <tex>key</tex> с первым и с последним элементами массива:
+
Затем воспользуемся двоичным поиском искомого элемента <tex>key</tex>, запустив его на той части массива, в которой он находится: на <tex>[0, x]</tex> или на <tex>[x + 1, n - 1]</tex>. Для определения нужной части массива сравним <tex>key</tex> с первым и с последним элементами массива:
 
<code>
 
<code>
  '''if''' key > a[0]              <font color="green">// Если key в левой части...</font>
+
  '''if''' key > a[0]              <font color="green">// Если key в левой части</font>
     l = 0
+
     l = -1
 
     r = x + 1
 
     r = x + 1
  '''if''' key < a[n]              <font color="green">// Если key в правой части...</font>
+
  '''if''' key < a[n]              <font color="green">// Если key в правой части</font>
     l = x + 1
+
     l = x  
     r = n + 1
+
     r = n
 
</code>
 
</code>
 
Время выполнения данного алгоритма {{---}} <tex>O(2\log n)=O(\log n)</tex>.
 
Время выполнения данного алгоритма {{---}} <tex>O(2\log n)=O(\log n)</tex>.
  
==='''Применение поиска на массиве, отсортированном по возрастанию, в конец которого приписан массив, отсортированный по убыванию'''===
 
  
Найдем индекс последнего элемента массива, отсортированного по возрастанию, воспользовавшись двоичным поиском, условие в <tex>if</tex> в котором изменено на <tex>a[m] > a[m - 1]</tex>. Тогда в <tex>l</tex> будет содержаться искомый индекс:
+
{{Задача
<code>
+
|definition = Массив образован путем приписывания в конец массива, отсортированного по возрастанию, массива, отсортированного по убыванию. Требуется максимально быстро найти элемент в таком массиве.
'''int''' l = 0
+
}}
'''int''' r = n + 1   
+
 
'''while''' l < r - 1                <font color="green">// Запускаем цикл...</font>
+
Найдем индекс последнего элемента массива, отсортированного по возрастанию, воспользовавшись [[Троичный_поиск|троичным поиском]], затем запустим левосторонний двоичный поиск для каждого массива отдельно: для элементов <tex>[0 \ldots x]</tex> и для элементов <tex>[x+1 \ldots n]</tex>, где в качестве <tex>x</tex> мы возьмем индекс максимума, найденный троичным поиском. Для массива, отсортированного по убыванию используем двоичный поиск, изменив условие в <code>'''if'''</code> на <tex>a[m] > key</tex>.
    m = (l + r) / 2            <font color="green">// m {{---}} середина области поиска.</font>
+
 
    '''if''' a[m] > a[m - 1]             <font color="green">// Сужение границ...</font>
+
Время выполнения алгоритма {{---}} <tex> O(\log n)</tex> (так как и бинарный поиск, и [[тернарный поиск]] работают за логарифмическое время с точностью до константы).
        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>O(3\log n)=O(\log n)</tex>.
 
  
 +
{{Задача
 +
|definition = Два отсортированных по возрастанию массива записаны один в конец другого. Требуется максимально быстро найти элемент в таком массиве.
 +
}}
  
==='''Применение поиска на двух отсортированных по возрастанию массивах, записанных один в конец другого'''===
+
Мы имеем массив, образованный из двух отсортированных подмассивов, записанных один в конец другого. Запустить сразу бинарный или тернарный поиски на таком массиве нельзя, так как массив не будет обязательно отсортированным и он не будет иметь <tex>1</tex> точку экстремума. Поэтому попробуем найти индекс последнего элемента левого массива, чтобы потом запустить бинарный поиск два раза на отсортированных массивах.
  
Мы имеем массив, образованный из двух отсортированных массивов, записанных один в конец другого. Рассмотрим разные примеры таких массивов (вертикальная черта означает границу между двумя маленькими массивами, образующими большой, никакой смысловой нагрузки она не несет, она нужна лишь для облегчения понимания):
+
Докажем, что найти этот индекс невозможно быстрее, чем за <tex>\Omega (n)</tex>. Возьмем возрастающий массив целых чисел, начиная с <tex>1</tex>. Он удовлетворяет условию задачи. Вставим в него <tex>0</tex> на любую позицию. Такой массив по-прежнему будет удовлетворять условию задачи. Следовательно, из-за того, что <tex>0</tex> может находиться на любой позиции, мы можем его найти лишь за <tex>\Omega (n)</tex>.
# <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(n)</tex> сравнений. Такой алгоритм на массиве <tex> \{ 1,2,3 \mid 4,5,6 \}</tex> должен будет убедиться, что элементы возрастают, но для этого ему придется сравнить все соседние элементы, потому что массив может быть таким: <tex> \{ 1,2,3,  4 \mid \textbf{0} ,6 \}</tex>. При этом все элементы, кроме пятого не меняются, значит, по другим элементам невозможно меньше, чем за <tex>O(n)</tex> определить, возрастает ли массив на всей своей длине или нет.
+
{{Задача
 +
|definition = Массив образован путем циклического сдвига массива, образованного приписыванием отсортированного по убыванию массива в конец отсортированного по возрастанию. Требуется максимально быстро найти элемент в таком массиве.
 +
}}
  
Для того, чтобы за <tex>O(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>) соответственно.
  
 +
Фактически, при поиске индексов минимума и максимума мы проверяем, возрастает или убывает массив на промежутке <tex> [ 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</tex>) или на <tex>a[m] > a[m + 1]</tex> (ответ будет записан в <tex>r</tex>) соответственно:
+
В случае же убывание-возрастание-убывание (<tex> \searrow \nearrow \searrow </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>
+
Время выполнения данного алгоритма {{---}} <tex>O(6\log n)=O(\log n)</tex>.
'''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''' min = r
 
</code>
 
Затем, в зависимости от расположения частей (можно узнать, сравнив <tex>min</tex> и <tex>max</tex>), запустим двоичный поиск для каждой части отдельно аналогично задаче о поиске элемента  на массиве, отсортированном по возрастанию, в конец которого приписан массив, отсортированный по убыванию.
 
  
Время выполнения данного алгоритма {{---}} <tex>O(5\log n)</tex>.
+
== Переполнение индекса середины ==
 +
В некоторых языках программирования присвоение <code>m = (l + r) / 2</code> приводит к переполнению. Вместо этого рекомендуется использовать <code>m = l + (r - l) / 2;</code> или эквивалентные выражения.<ref>https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html</ref>
  
 
== См. также ==
 
== См. также ==
Строка 161: Строка 139:
  
 
== Источники информации ==
 
== Источники информации ==
* Д. Кнут - Искусство программирования (Том 3, 2-е издание)
+
* Д. Кнут {{---}} Искусство программирования (Том 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://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://habrahabr.ru/post/146228/ Типичные ошибки при написании бинарного поиска]
* [http://algolist.manual.ru/search/advbin.php| Бинарный поиск на algolist]
+
* [http://algolist.manual.ru/search/advbin.php Бинарный поиск на algolist]
 +
 
 +
== Примечания ==
 +
<references/>
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Алгоритмы поиска]]
 
[[Категория: Алгоритмы поиска]]

Текущая версия на 19:39, 4 сентября 2022

Целочисленный двоичный поиск (бинарный поиск) (англ. binary search) — алгоритм поиска объекта по заданному признаку в множестве объектов, упорядоченных по тому же самому признаку, работающий за логарифмическое время.

Задача:
Пусть нам дан упорядоченный массив, состоящий только из целочисленных элементов. Требуется найти позицию, на которой находится заданный элемент.


Схема бинарного поиска

Принцип работы

Двоичный поиск заключается в том, что на каждом шаге множество объектов делится на две части и в работе остаётся та часть множества, где находится искомый объект. Или же, в зависимости от постановки задачи, мы можем остановить процесс, когда мы получим первый или же последний индекс вхождения элемента. Последнее условие — это левосторонний/правосторонний двоичный поиск.

Правосторонний/левосторонний целочисленный двоичный поиск

Для простоты дальнейших определений будем считать, что [math]a[-1] = -\infty[/math] и что [math]a[n] = +\infty[/math] (массив нумеруется с [math]0[/math]).


Определение:
Правосторонний бинарный поиск (англ. rightside binary search) — бинарный поиск, с помощью которого мы ищем [math] \max\limits_{i \in [-1,n-1]} \{i \mid a[i] \leqslant x\} [/math], где [math]a[/math] — массив, а [math]x[/math] — искомый ключ


Определение:
Левосторонний бинарный поиск (англ. leftside binary search) — бинарный поиск, с помощью которого мы ищем [math] \min\limits_{i \in [0,n]}\{i \mid a[i] \geqslant x\} [/math], где [math]a[/math] — массив, а [math]x[/math] — искомый ключ


Использовав эти два вида двоичного поиска, мы можем найти отрезок позиций [math][l,r][/math] таких, что [math]\forall i \in [l,r] : a[i] = x[/math] и [math] \forall i \notin [l,r] : a[i] \neq x [/math]

Пример:

Задан отсортированный массив [math][1, 2, 2, 2, 2, 3, 5, 8, 9, 11], x = 2[/math].

Правосторонний поиск двойки выдаст в результате [math]4[/math], в то время как левосторонний выдаст [math]1[/math] (нумерация с нуля).

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

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

Алгоритм двоичного поиска

Идея поиска заключается в том, чтобы брать элемент посередине, между границами, и сравнивать его с искомым. Если искомое больше(в случае правостороннего — не меньше), чем элемент сравнения, то сужаем область поиска так, чтобы новая левая граница была равна индексу середины предыдущей области. В противном случае присваиваем это значение правой границе. Проделываем эту процедуру до тех пор, пока правая граница больше левой более чем на [math]1[/math].

Код

int binSearch(int[] a, int key):   // Запускаем бинарный поиск
    int l = -1                      // l, r — левая и правая границы
    int r = len(a)    
    while l < r - 1                // Запускаем цикл
        m = (l + r) / 2            // m — середина области поиска
        if a[m] < key
            l = m
        else 
            r = m                  // Сужение границ
    return r

Инвариант цикла: правый индекс не меньше искомого элемента, а левый — строго меньше (т.к значение [math]m[/math] присваевается левой границе [math]l[/math], только тогда, когда [math]a[m][/math] строго меньше искомого элемента [math]key[/math]), тогда если [math]r = l + 1[/math] (что эквивалентно [math]r-l=1[/math]), то понятно, что [math]r[/math] — самое левое вхождение искомого элемента (так как предыдущие элементы уже меньше искомого элемента)


В случае правостороннего поиска изменится знак сравнения при сужении границ на [math]a[m] \leqslant k[/math], а возвращаемой переменной станет [math]l[/math].

Несколько слов об эвристиках

Эвристика с завершением поиска, при досрочном нахождении искомого элемента

Заметим, что если нам необходимо просто проверить наличие элемента в упорядоченном множестве, то можно использовать любой из правостороннего и левостороннего поиска. При этом будем на каждой итерации проверять "не попали ли мы в элемент, равный искомому", и в случае попадания заканчивать поиск.

Эвристика с запоминанием ответа на предыдущий запрос

Пусть дан отсортированный массив чисел, упорядоченных по неубыванию. Также пусть запросы приходят в таком порядке, что каждый следующий не меньше, чем предыдущий. Для ответа на запрос будем использовать левосторонний двоичный поиск. При этом после того как обработался первый запрос, запомним чему равно [math]l[/math], запишем его в переменную [math]startL[/math]. Когда будем обрабатывать следующий запрос, то проинициализируем левую границу как [math]startL[/math]. Заметим, что все элементы, которые лежат не правее [math]startL[/math], строго меньше текущего искомого элемента, так как они меньше предыдущего запроса, а значит и меньше текущего. Значит инвариант цикла выполнен.

Применение двоичного поиска на некоторых неотсортированных массивах

Задача:
Пусть отсортированный по возрастанию массив из [math]n[/math] элементов [math]a[0 \ldots n - 1][/math], все элементы которого различны, был циклически сдвинут, требуется максимально быстро найти элемент в таком массиве.


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

int l = -1
int r = len(a)   
while l < r - 1                // С помощью бинарного поиска найдем максимум на массиве
    m = (l + r) / 2            // m — середина области поиска
    if a[m] > a[n - 1]         // Сужение границ
        l = m
    else 
        r = m
int x = l                      // x — искомый индекс.

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

if key > a[0]               // Если key в левой части
    l = -1
    r = x + 1
if key < a[n]               // Если key в правой части
    l = x 
    r = n

Время выполнения данного алгоритма — [math]O(2\log n)=O(\log n)[/math].


Задача:
Массив образован путем приписывания в конец массива, отсортированного по возрастанию, массива, отсортированного по убыванию. Требуется максимально быстро найти элемент в таком массиве.


Найдем индекс последнего элемента массива, отсортированного по возрастанию, воспользовавшись троичным поиском, затем запустим левосторонний двоичный поиск для каждого массива отдельно: для элементов [math][0 \ldots x][/math] и для элементов [math][x+1 \ldots n][/math], где в качестве [math]x[/math] мы возьмем индекс максимума, найденный троичным поиском. Для массива, отсортированного по убыванию используем двоичный поиск, изменив условие в if на [math]a[m] \gt key[/math].

Время выполнения алгоритма — [math] O(\log n)[/math] (так как и бинарный поиск, и тернарный поиск работают за логарифмическое время с точностью до константы).


Задача:
Два отсортированных по возрастанию массива записаны один в конец другого. Требуется максимально быстро найти элемент в таком массиве.


Мы имеем массив, образованный из двух отсортированных подмассивов, записанных один в конец другого. Запустить сразу бинарный или тернарный поиски на таком массиве нельзя, так как массив не будет обязательно отсортированным и он не будет иметь [math]1[/math] точку экстремума. Поэтому попробуем найти индекс последнего элемента левого массива, чтобы потом запустить бинарный поиск два раза на отсортированных массивах.

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


Задача:
Массив образован путем циклического сдвига массива, образованного приписыванием отсортированного по убыванию массива в конец отсортированного по возрастанию. Требуется максимально быстро найти элемент в таком массиве.


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

Фактически, при поиске индексов минимума и максимума мы проверяем, возрастает или убывает массив на промежутке [math] [ m - 1 ; m ] [/math], а затем, в зависимости от того, что мы ищем, мы либо поднимаемся, либо опускаемся по этому промежутку возрастания (убывания). Однако при таком решении могут быть неправильно найдены значения минимума или максимума. Рассмотрим случаи, когда они будут неправильно найдены. Определить, какого вида наш массив возможно, сравнив первые два элемента массива.

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

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

Затем, в зависимости от типа нашего массива, запустим бинарный поиск три раза на каждом промежутке.

Время выполнения данного алгоритма — [math]O(6\log n)=O(\log n)[/math].

Переполнение индекса середины

В некоторых языках программирования присвоение m = (l + r) / 2 приводит к переполнению. Вместо этого рекомендуется использовать m = l + (r - l) / 2; или эквивалентные выражения.[1]

См. также

Источники информации

Примечания