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

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

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

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

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

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

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

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

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

Применение

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

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

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

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

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

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

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

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

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

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

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

См. также

Ссылки

Литература

  1. Вирт Н. Алгоритмы+структуры данных= программы. — М.: «Мир», 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)) компромиссный подход к решению ряда задач в… … Википедия

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

mid = (left + right)/2

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

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

left = 0, right = 19

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

mid = (19+0)/2=9

Сравниваем значение по этому индексу с искомым:

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

mid = (9+19)/2=14

Сравниваем значение по этому индексу с искомым:

84 > 82

Сдвигаем правую границу:

right = mid = 14

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

mid = (9+14)/2=11

Сравниваем значение по этому индексу с искомым:

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

mid = (11+14)/2=12

Сравниваем значение по этому индексу с искомым:

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

mid = (12+14)/2=13

Сравниваем значение по этому индексу с искомым:

82 = 82

Решение найдено!

Чтобы уменьшить количество шагов поиска можно сразу смещать границы поиска на элемент, следующий за серединой отрезка:

left = mid + 1
right = mid — 1

Ссылка на основную публикацию
Что делать если ничего не скачивается
Сегодняшняя статья будет посвящена такой стандартной и даже банальной проблеме, как нежелание браузера сохранять файлы с интернета. Вроде как все...
Часы с функцией диктофона
Классические часы с секундной стрелкой; Цифровые часы (поддержка 12/24ч форматов, для смены формата сделайте двойной тап по цифрам); Диктофон (поддержка...
Часы с которых можно звонить детские
Ребенка, который самостоятельно посещает школу или гуляет с друзьями, подстерегает много опасностей. Решить эту проблему помогут технологичные детские умные часы...
Что делать если перегревается процессор на ноутбуке
Когда сильно греется процессор ноутбука, следует сначала проверить всё ли в порядке с его программным обеспечением. Если проверка ПО не...
Adblock detector