Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании.
Частным случаем двоичного поиска является метод бисекции, который применяется для поиска корней заданной непрерывной функции на заданном отрезке.
Поиск элемента в отсортированном массиве
Пример кода на языке программирования 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
в цепочке существует в нескольких экземплярах, находило не любой, а обязательно первый (как вариант: последний; следующий за последним). Данная версия кода в такой ситуации находит первый из равных.
Учёный Йон Бентли утверждает, что 90% студентов, разрабатывая двоичный поиск, забывают учесть какое-либо из этих требований. И даже в код, написанный самим Йоном и ходивший из книги в книгу, вкралась ошибка: код не стоек к переполнениям[1].
Приложения
Практические приложения метода двоичного поиска разнообразны:
- Широкое распространение в информатике применительно к поиску в структурах данных. Например, поиск в массивах данных осуществляется по ключу, присвоенному каждому из элементов массива (в простейшем случае сам элемент является ключом).
- Также его применяют в качестве численного метода для нахождения приближённого решения уравнений.
- Метод бисекции используется для поиска численных решений уравнений.
- Метод используется для нахождения экстремума целевой функции и в этом случае является методом условной одномерной оптимизации. Когда функция имеет вещественный аргумент, найти решение с точностью до можно за время . Когда аргумент дискретен, и изначально лежит на отрезке длины N, поиск решения займёт времени. Наконец, для поиска экстремума, скажем для определённости минимума, на очередном шаге отбрасывается тот из концов рассматриваемого отрезка, значение в котором максимально.
См. также
Ссылки
- Материал на сайте algolist
Примечания
Литература
- Ананий В. Левитин. Глава 4. Метод декомпозиции: Бинарный поиск // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. — М.: «Вильямс», 2006. — С. 180-183. — ISBN 5-8459-0987-2
- Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров. — М.: Мир, 1998.
- Бахвалов Н. С., Жидков Н. П., Кобельков Г. Г. Численные методы. — 8-е изд. — М.: Лаборатория Базовых Знаний, 2000.
- Вирт Н. Алгоритмы + структуры данных = программы. — М.: «Мир», 1985. — С. 28.
- Волков Е. А. Численные методы. — М.: Физматлит, 2003.
- Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
- Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4
- Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
- Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. — Энергоатомиздат, 1972.
- Максимов Ю. А., Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
- Роберт Седжвик. Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. — СПб.: ДиаСофтЮП, 2003. — С. 672. — ISBN 5-93772-081-4