Бинарный поиск

Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе). Также применяется для нахождения заданного значения монотонной(невозрастающей или неубывающей) функции. Поиск основывается на теореме о промежуточных значениях. Используется в информатике, вычислительной математике и математическом программировании.

Описание метода

Сформулируем основные теоремы:

Теорема (Больцано — Коши). Пусть функция $f(x)\in\mathrm{C}([a,\;b]): \; f(a)=A,\; f(b)=B$, тогда $\forall C \in [A,\;B]\; \exist c\in[a,\;b]:\;f(c)=C$. Следствие. Пусть функция $f(x)\in\mathrm{C}([a,\;b])\!$, тогда если $f(a)>0, f(b)\!<0$, то $\exist c\in[a,\;b]:\;f(c)=0$.

Таким образом, если мы ищем ноль, то на концах отрезка функция должна быть разных знаков. Разделим отрезок пополам и возьмём ту из половинок, для которой на концах функция по-прежнему принимает значения разных знаков. Если серединная точка оказалось искомым нулём, то процесс завершается.

Если задана точность вычисления $\varepsilon \!$, то процедуру следует продолжать до тех пор, пока длина отрезка не станет меньше $\varepsilon$.

Для поиска произвольного значения достаточно вычесть из значения функции искомое значение и искать ноль получившейся функции.

Поиск элемента отсортированного массива

Для поиска элемента массива A, отсортированного в возрастающем порядке, применяется следующий алгоритм ^[1] :

  i := 1;
  j := n; {число элементов массива}
  repeat
      k := (i+j) div 2; {разделить пополам интервал просмотра}
      if x > A[k] then
        i := k+1
      else
        j := k-1;
  until (A[k]=x) or (i>j);

Применение

Практическое применение метода двоичного поиска очень широко. Перечислим основные способы:

• Самое широкое распространение метод получил в информатике для навигации (поиска) в структурах данных.
• Также его применяют в качестве численного метода для нахождения приближённого решения уравнений.
• Метод служит для нахождения экстремума целевой функции и в этом случае является методом условной одномерной оптимизации.

Когда функция имеет вещественный аргумент, найти решение с точностью до $\varepsilon\!$ можно за время $log_2\alpha\!$, где $\alpha = {1\over \varepsilon}\!$. Когда аргумент дискретен, и изначально лежит на отрезке длины N, поиск решения займёт $1 + \log_2N\!$ времени.

Применительно к массивам данных, поиск осуществляется по ключу, присвоенному каждому из элементов массива (в простейшем случае сам элемент является ключом).

Двоичный поиск как численный метод решения уравнений предполагает поиск нуля, о чём уже было сказано в описании.

Наконец, для поиска экстремума, скажем для определённости минимума, на очередном шаге отбрасывается тот из концов рассматриваемого отрезка, значение в котором максимально.

Поиск значения монотонной функции

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

Пускай переменные $L_b\,\!$ и $U_b\,\!$ содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Исследования начинаются со среднего элемента отрезка. Если искомое значение меньше среднего элемента, осуществляется переход к поиску в верхней половине отрезка, где все элементы меньше только что проверенного, то есть значением $U_b\,\!$ становится $\left( M - 1 \right)\,\!$ и на следующей итерации исследуется только половина массива. Т.о., в результате каждой проверки область поиска сужается вдвое.

Например, если длина массива равна 1023, после первого сравнения область сужается до 511 элементов, а после второй — до 255.Т.о. для поиска в массиве из 1023 элементов достаточно 10 сравнений.

l = леваяГраница - 1
r = праваяГраница + 1
while (r - l > 1) {
  середина = (l+r) / 2
  if (массив[середина] < значение)
     l = середина
  else
     r = середина
 } 
 if (массив[r] ≠ значение)
   return -1 // элемент не найден
 else
   return r

См. также

• Троичный поиск
• Метод дихотомии

Ссылки

• Материал на сайте algolist
• Двоичный поиск и объяснение кодекс в C++(англ.)

Литература

1. ↑ Вирт Н. Алгоритмы+структуры данных= программы. — М.: «Мир», 1985. — С. 28.

• Ананий В. Левитин Глава 4. Метод декомпозиции: Бинарный поиск // [ttp://www.williamspublishing.com/Books/5-8459-0987-2.html Алгоритмы: введение в разработку и анализ] = ntroduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 180-183. — ISBN 0-201-74395-7
• Амосов А.А., Дубинский Ю. А., Копченова Н.П. Вычислительные методы для инженеров. — М.: Мир, 1998.
• Бахвалов Н.С., Жидков Н.П., Кобельков Г.Г. Численные методы. — 8-е изд.. — М.: Лаборатория Базовых Знаний, 2000.
• Волков Е.А. Численные методы. — М.: Физматлит, 2003.
• Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1
• Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
• Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — Энергоатомиздат, 1972.
• Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.