Двоичный поиск

Материал из Википедии — свободной энциклопедии

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

[править] Описание метода

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

Теорема.
Пусть функция $f(x)\in\mathrm{C}([a,\;b])\!$ , тогда если $f(a)>0, f(b)\!<0$ , то $\exist c\in[a,\;b]:\;f(c)=0$ .
Следствие (теорема о промежуточных значениях).
Пусть функция $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$ .

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

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

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

[править] Применение

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

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

Когда функция имеет вещественный аргумент, найти решение с точностью до $\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 сравнений.

int function BinarySearch (Array A, int Lb, int Ub, int Key);
  begin
  do forever
    M = Lb + (Ub-Lb)/2;
    if (Key < A[M]) then
      Ub = M - 1;
    else if (Key > A[M]) then
      Lb = M + 1;
    else
      return M;
    if (Lb > Ub) then
    return -1;
  end;

Обычной ошибкой является вычисление среднего элемента по формуле $M = \frac{L_b + U_b}{2}\!$ . Ошибка состоит в том, что если числа $L_b\!$ и $U_b\!$ достаточно велики, то на реальных ЭВМ из-за переполнения, возникшего при сложении $L_b\!$ и $U_b\!$ значение M будет вычислено неверно

[править] Ссылки

[править] Литература

Ананий В. Левитин Глава 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.
Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — Энергоатомиздат, 1972.
Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.