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

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

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

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

Поиск элемента в отсортированном массиве[править | править вики-текст]

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

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

  • Что будет, если first и last по отдельности умещаются в свой тип, а first+last — нет?[1]
  • Будет ли работать на пустом массиве (n=0)?
  • Способен ли код находить отсутствующие значения? У некоторых программистов написанный «с листа» двоичный поиск в такой ситуации зацикливается — и они этого не осознают, пока тестирование не даст ошибку.
  • Способен ли код найти первый и последний элемент? Возможна и обратная ошибка — выход за границы массива, если x задать слишком большим или слишком маленьким.
  • Иногда требуется, чтобы, если x в цепочке существует в нескольких экземплярах, находило не любой, а обязательно первый (как вариант: последний; либо вообще не x, а следующий за ним элемент).[2] Данная версия кода в такой ситуации находит первый из равных.

Учёный Йон Бентли утверждает, что 90 % студентов, разрабатывая двоичный поиск, забывают учесть какое-либо из этих требований. И даже в код, написанный самим Йоном и ходивший из книги в книгу, вкралась ошибка: код не стоек к переполнениям[1].

Приложения[править | править вики-текст]

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

  • Широкое распространение в информатике применительно к поиску в структурах данных. Например, поиск в массивах данных осуществляется по ключу, присвоенному каждому из элементов массива (в простейшем случае сам элемент является ключом).
  • Также его применяют в качестве численного метода для нахождения приближённого решения уравнений (см. Метод бисекции).
  • Метод используется для нахождения экстремума целевой функции и в этом случае является методом условной одномерной оптимизации. Когда функция имеет вещественный аргумент, найти решение с точностью до \varepsilon можно за время \log_2 1 / \varepsilon. Когда аргумент дискретен, и изначально лежит на отрезке длины N, поиск решения займёт 1 + \log_2N\! времени. Наконец, для поиска экстремума, скажем, для определённости минимума, на очередном шаге отбрасывается тот из концов рассматриваемого отрезка, значение в котором максимально.

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken // Joshua Bloch, Google Research; перевод — Почти во всех реализациях двоичного поиска и сортировки слиянием есть ошибка
  2. В C++ std::lower_bound находит первое вхождение x, а std::upper_bound — элемент, следующий за x.

Литература[править | править вики-текст]

  • Ананий В. Левитин. Глава 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.

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