- Бинарный поиск
-
Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе). Также применяется для нахождения заданного значения монотонной(невозрастающей или неубывающей) функции. Поиск основывается на теореме о промежуточных значениях. Используется в информатике, вычислительной математике и математическом программировании.
Содержание
Описание метода
Сформулируем основные теоремы:
Теорема (Больцано — Коши).
Пусть функция , тогда .
Следствие.
Пусть функция , тогда если , то .Таким образом, если мы ищем ноль, то на концах отрезка функция должна быть разных знаков. Разделим отрезок пополам и возьмём ту из половинок, для которой на концах функция по-прежнему принимает значения разных знаков. Если серединная точка оказалось искомым нулём, то процесс завершается.
Если задана точность вычисления , то процедуру следует продолжать до тех пор, пока длина отрезка не станет меньше .
Для поиска произвольного значения достаточно вычесть из значения функции искомое значение и искать ноль получившейся функции.
Поиск элемента отсортированного массива
Для поиска элемента массива 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);
Применение
Практическое применение метода двоичного поиска очень широко. Перечислим основные способы:
- Самое широкое распространение метод получил в информатике для навигации (поиска) в структурах данных.
- Также его применяют в качестве численного метода для нахождения приближённого решения уравнений.
- Метод служит для нахождения экстремума целевой функции и в этом случае является методом условной одномерной оптимизации.
Когда функция имеет вещественный аргумент, найти решение с точностью до можно за время , где . Когда аргумент дискретен, и изначально лежит на отрезке длины N, поиск решения займёт времени.
Применительно к массивам данных, поиск осуществляется по ключу, присвоенному каждому из элементов массива (в простейшем случае сам элемент является ключом).
Двоичный поиск как численный метод решения уравнений предполагает поиск нуля, о чём уже было сказано в описании.
Наконец, для поиска экстремума, скажем для определённости минимума, на очередном шаге отбрасывается тот из концов рассматриваемого отрезка, значение в котором максимально.
Поиск значения монотонной функции
Поиск значения монотонной функции, записанной в массиве, заключается в сравнении срединного элемента массива с искомым значением, и повторением алгоритма для той или другой половины, в зависимости от результата сравнения.
Пускай переменные и содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Исследования начинаются со среднего элемента отрезка. Если искомое значение меньше среднего элемента, осуществляется переход к поиску в верхней половине отрезка, где все элементы меньше только что проверенного, то есть значением становится и на следующей итерации исследуется только половина массива. Т.о., в результате каждой проверки область поиска сужается вдвое.
Например, если длина массива равна 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
См. также
Ссылки
Литература
- ↑ Вирт Н. Алгоритмы+структуры данных= программы. — М.: «Мир», 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.
Wikimedia Foundation. 2010.