Что такое бинарный поиск

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

Теорема (Больцано — Коши).
Пусть функция , тогда .
Следствие.
Пусть функция , тогда если , то .

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

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

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

Содержание

Поиск элемента отсортированного массива
Применение
Поиск значения монотонной функции
См. также
Ссылки
Литература
Смотреть что такое «Бинарный поиск» в других словарях:

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

Для поиска элемента массива A, отсортированного в возрастающем порядке, применяется следующий алгоритм [1] :

Применение

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

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

Когда функция имеет вещественный аргумент, найти решение с точностью до можно за время , где . Когда аргумент дискретен, и изначально лежит на отрезке длины N, поиск решения займёт времени.

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

Двоичный поиск как численный метод решения уравнений предполагает поиск нуля, о чём уже было сказано в описании.

Наконец, для поиска экстремума, скажем для определённости минимума, на очередном шаге отбрасывается тот из концов рассматриваемого отрезка, значение в котором максимально.

Поиск значения монотонной функции

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

Пускай переменные и содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Исследования начинаются со среднего элемента отрезка. Если искомое значение меньше среднего элемента, осуществляется переход к поиску в верхней половине отрезка, где все элементы меньше только что проверенного, то есть значением становится и на следующей итерации исследуется только половина массива. Т.о., в результате каждой проверки область поиска сужается вдвое.

Читайте также: Нет изображения на экране монитора

Например, если длина массива равна 1023, после первого сравнения область сужается до 511 элементов, а после второй — до 255.Т.о. для поиска в массиве из 1023 элементов достаточно 10 сравнений.

См. также

Ссылки

Литература

↑Вирт Н. Алгоритмы+структуры данных= программы. — М.: «Мир», 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 .

Смотреть что такое «Бинарный поиск» в других словарях:

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

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

Кубический сплайн — Некоторая функция f(x) задана на отрезке , разбитом на части , . Кубическим сплайном дефекта 1 называется функция , которая: на каждом отрезке является многочленом степени не выше третьей; имеет непрерывные первую и вторую производные на всём… … Википедия

Читайте также: Найти трек по словам из песни

Задача поиска наибольшей увеличивающейся подпоследовательности — состоит в отыскании наиболее длинной возрастающей подпоследовательности в данной последовательности элементов. Содержание 1 Постановка задачи 2 Родственные алгоритмы … Википедия

Возрастающая подпоследовательность — Задача поиска наибольшей увеличивающейся подпоследовательности состоит в отыскании наиболее длинной возрастающей подпоследовательности в данной последовательности элементов. Содержание 1 Постановка задачи 2 Родственные алгоритмы … Википедия

Суффиксный массив — Суффиксный массив лексикографически отсортированный массив всех суффиксов строки. Эта структура данных была разработана Джином Майерсом и Уди Манбером как более экономная альтернатива суффиксному дереву с точки зрения необходимой памяти.… … Википедия

Standard Template Library — Стандартная библиотека шаблонов (STL) (англ. Standard Template Library) набор согласованных обобщенных алгоритмов, контейнеров, средств доступа к их содержимому и различных вспомогательных функций. Стандартная библиотека шаблонов до включения в… … Википедия

PECompact — Скри … Википедия

Space-time tradeoff — Space time trade off («выбор оптимального соотношения „место время“ (англ. space time trade off)», или, иначе, «выбор оптимального соотношения „время память“» (англ. time memory trade off)) компромиссный подход к решению ряда задач в… … Википедия

Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и … Википедия

Бинарный поиск — классический алгоритм. На вход алгоритм принимает отсортированный массив чисел и число для поиска. На выходе — индекс этого числа в массиве.

Алгоритмически это выглядит так:

Запоминаем левую L и правую R границы массива (индексы, а не значения)
Берем индекс M посередине между L и R
Если значение массива по индексу M меньше нужного — L меняем на M, если больше — R меняем на M
Возвращаемся на шаг 2

Таким образом мы на каждом шаге алгоритма сужаем область поиска в 2 раза. Этот алгоритм имеет сложность O(log(n)).

В теории все просто, но на практике возникают проблемы.

Приведу сразу свою реализацию, а потом разберем все проблемы.

Распространенная ошибка реализации — переполнение типа при вычислении середины интервала. Именно поэтому середина вычисляется так

Читайте также: Официальный сайт прошивка планшета асер

Еще одна проблема — выход из алгоритма. Нужно правильно обрабатывать ситуацию, когда интервал поиска свелся к двум соседним индексам. Я для наглядности вместо хитрых операций с индексами вынес эту ситуацию в отдельный блок кода

Так же можно добавить дополнительную оптимизацию для ситуации, когда value заведомо слишком маленькое или большое. Будут такие проверки в начале метода:

Бинарный поиск производится в упорядоченном массиве.

При бинарном поиске искомый ключ сравнивается с ключом среднего элемента в массиве. Если они равны, то поиск успешен. В противном случае поиск осуществляется аналогично в левой или правой частях массива.

Алгоритм может быть определен в рекурсивной и нерекурсивной формах.

Бинарный поиск также называют поиском методом деления отрезка пополам или дихотомии .

Количество шагов поиска определится как

где n-количество элементов,
↑ — округление в большую сторону до ближайшего целого числа.

На каждом шаге осуществляется поиск середины отрезка по формуле

mid = (left + right)/2

Если искомый элемент равен элементу с индексом mid, поиск завершается.
В случае если искомый элемент меньше элемента с индексом mid, на место mid перемещается правая граница рассматриваемого отрезка, в противном случае — левая граница.

Подготовка . Перед началом поиска устанавливаем левую и правую границы массива:

left = 0, right = 19

Шаг 1 . Ищем индекс середины массива (округляем в меньшую сторону):

mid = (19+0)/2=9