18. Двоичный (бинарный) поиск

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

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

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

Пример кода на языке программирования Cи для поиска элемента x в массиве a[n], отсортированного в возрастающем порядке:

size_t first = 0; /* Первый элемент в массиве */

size_t last = n; /* Элемент в массиве, СЛЕДУЮЩИЙ ЗА последним */

/* Если просматриваемый участок непустой, first<last */

size_t mid;

if (n == 0)

{ /* массив пуст */

}

else if (a[0] > x)

{ /* не найдено; если вам надо вставить его со сдвигом - то в позицию 0 */

} else if (a[n - 1] < x)

{ /* не найдено; если вам надо вставить его со сдвигом - то в позицию n */

}

while (first < last)

{ /* ВНИМАНИЕ! В отличие от более простого (first+last)/2, этот код стоек к переполнениям.

Если first и last знаковые, возможен код (unsigned)(first+last) >> 1. mid = first + (last - first) / 2;

if (x <= a[mid])

{ last = mid; }

else

{ first = mid + 1; } }

/* Если проверка n==0 в начале опущена - значит, тут раскомментировать! */

if (/*n!=0 &&*/ a[last] == x)

{ /* Искомый элемент найден. last - искомый индекс */

} else { /* Искомый элемент не найден. Но если вам вдруг надо его вставить со сдвигом, то его место - last. */

}

Несмотря на то, что код достаточно прост, в нём есть несколько ловушек.

Что будет, если first и last по отдельности умещаются в свой тип, а first+last — нет?

Будет ли работать на пустом массиве (n=0)?

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

Практические приложения метода двоичного поиска разнообразны:

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

Также его применяют в качестве численного метода для нахождения приближённого решения уравнений.

Метод бисекции используется для поиска численных решений уравнений.

Метод используется для нахождения экстремума целевой функции и в этом случае является методом условной одномерной оптимизации. Когда функция имеет вещественный аргумент, найти решение с точностью до ε можно за время log ₂1 / ε. Когда аргумент дискретен, и изначально лежит на отрезке длины N, поиск решения займёт 1+log 2N времени. Наконец, для поиска экстремума, скажем для определённости минимума, на очередном шаге отбрасывается тот из концов рассматриваемого отрезка, значение в котором максимально.