Бинарный поиск производится в упорядоченном массиве.
При бинарном поиске искомый ключ сравнивается с ключом среднего элемента в массиве. Если они равны, то поиск успешен. В противном случае поиск осуществляется аналогично в левой или правой частях массива.
Алгоритм может быть определен в рекурсивной и нерекурсивной формах.
Бинарный поиск также называют поиском методом деления отрезка пополам или дихотомии .
Количество шагов поиска определится как
где n-количество элементов,
↑ — округление в большую сторону до ближайшего целого числа.
На каждом шаге осуществляется поиск середины отрезка по формуле
Если искомый элемент равен элементу с индексом mid, поиск завершается.
В случае если искомый элемент меньше элемента с индексом mid, на место mid перемещается правая граница рассматриваемого отрезка, в противном случае — левая граница. 
- Подготовка . Перед началом поиска устанавливаем левую и правую границы массива:
left = 0, right = 19
Шаг 1 . Ищем индекс середины массива (округляем в меньшую сторону):
Сравниваем значение по этому индексу с искомым:
69
Шаг 2 . Ищем индекс середины массива (округляем в меньшую сторону):
Сравниваем значение по этому индексу с искомым:
84 > 82
Сдвигаем правую границу:
right = m >
Шаг 3 . Ищем индекс середины массива (округляем в меньшую сторону):
Сравниваем значение по этому индексу с искомым:
78
Шаг 4 . Ищем индекс середины массива (округляем в меньшую сторону):
Сравниваем значение по этому индексу с искомым:
80
Шаг 5 . Ищем индекс середины массива (округляем в меньшую сторону):
Сравниваем значение по этому индексу с искомым:
82 = 82
Решение найдено!
Чтобы уменьшить количество шагов поиска можно сразу смещать границы поиска на элемент, следующий за серединой отрезка:
left = mid + 1
right = mid — 1
Сегодня мы и изучим его. Также попытаемся ответить на такие вопросы: как бинарный поиск работает в программе, плюсы и минусы его использования у себя в коде и в каких структурах данных можно его применять, а в каких нет. Поехали!
Что такое бинарный поиск
Линейный поиск по сравнению с бинарным — дешевая подделка. Бинарный поиск — очень быстрый алгоритм с не сложной реализацией, который находит элемент с определенным значением в уже отсортированном массиве.
Очень важно помнить! Алгоритм будет работать правильно, только с отсортированным массивом. А если по случайности вы забыли отсортировать массив перед его использованием, то в большинстве случаев тот ответ, который подсчитал алгоритм, будет неверным.
Принцип работы бинарного поиска
Давайте рассмотрим задачку, чтобы понять как работает алгоритм.
Охранной службе морского флота поступило сообщение о том, что некто пытается пронести на корабль бомбу. Диверсант пока находится у причала. Допустим, что в нашем распоряжении имеется прибор, который может определить, есть ли бомба в комнате. Необходимо как можно быстрее определить, у кого находится бомба.
Самым легким и самым долгим по времени решением, будет поочередная проверка пассажиров в комнате с прибором (это линейный поиск). Но это слишком долго.
Давайте сделаем по-другому. Поделим пополам всех пассажиров и разведем их по двум комнатам. Так с помощью прибора мы сможем узнать, в какой из двух комнат находится бомба. В итоге такого маневра мы уменьшим число подозреваемых в два раза. С остальным числом подозреваемых сделаем также: разделим их на две группы и разместим в разных комнатах. Так продолжаем, пока не узнаем кто диверсант.
В задаче выше охранники использовали алгоритм двоичного поиска для нахождения диверсанта. В обычной программе принцип работы бинарного поиска такой же, как и в примере, выше.
Как создать бинарный поиск в C++
Давайте посмотрим как работает бинарный поиск на примере.В примере ниже в строке 9 мы создали массив arr на 10 элементов и в строке 12 предложили пользователю с клавиатуры заполнить его ячейки.
В строке 20 мы предлагаем пользователю ввести ключ (который нужно будет найти в массиве), а дальше мы с бинарным поиском проверим массив на наличие введенного ключа пользователем. Если мы найдем ключ в массиве, то выведем индекс ячейки, в которой находится ключ.
Сформулируем основные теоремы:
| Теорема (Больцано — Коши). Пусть функция  , тогда  . Следствие. Пусть функция  , тогда если  , то  . |
Таким образом, если мы ищем ноль, то на концах отрезка функция должна быть разных знаков. Разделим отрезок пополам и возьмём ту из половинок, для которой на концах функция по-прежнему принимает значения разных знаков. Если серединная точка оказалось искомым нулём, то процесс завершается.
Если задана точность вычисления 
, то процедуру следует продолжать до тех пор, пока длина отрезка не станет меньше 
.
Для поиска произвольного значения достаточно вычесть из значения функции искомое значение и искать ноль получившейся функции.
Поиск элемента отсортированного массива
Для поиска элемента массива 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)) компромиссный подход к решению ряда задач в… … Википедия
Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и … Википедия