6 582 
Оставить комментарий
Сохранить статью:
О чем речь? Бинарный поиск – это алгоритм поиска элемента в отсортированном массиве данных. Этот метод является довольно популярным в программировании и может быть реализован на разных языках: от С до Python.
На что обратить внимание? Несмотря на свою простоту, у бинарного поиска есть ряд сложностей в реализации. Даже опытные программисты часто ошибаются при работе с данным алгоритмом.
В статье рассказывается:
- Понятие бинарного поиска
- Принцип работы бинарного поиска на примере
- Реализация бинарного поиска в программировании
- Проблемы бинарного поиска
-
Пройди тест и узнай, какая сфера тебе подходит:
айти, дизайн или маркетинг.Бесплатно от Geekbrains
Понятие бинарного поиска
Бинарным (или двоичным) называют поиск элемента упорядоченного множества через многократное деление этого множества пополам. Искомый элемент всегда будет оказываться в одной из двух частей. Поиск прекращается, когда обнаруживается совпадение граничного элемента между двумя разделенными блоками с заданным, или когда заданный элемент не обнаруживается вовсе.
Реализация этого метода возможна только применимо к отсортированным множествам. Последовательно разбивая такой массив данных на две части, алгоритм каждый раз ищет заданный элемент только в одной половине.
В целом метод бинарного поиска можно описать следующим образом. Сначала в возрастающем или убывающем множестве определяется среднее значение, после чего оно сравнивается с искомым. При совпадении заданного и центрального элемента поиск прекращается — элемент считается найденным. В случае несовпадения значений создается новый массив значений соответственно слева и справа от среднего, и процедура повторяется уже на данном массиве.
Принцип работы бинарного поиска на примере
Принцип достаточно прост. Множество данных предварительно сортируется (чаще всего по возрастанию). Затем для поиска конкретных элементов выполняется следующая последовательность действий:
- Вычисляется среднее значение массива.
- Значение полученного элемента сравнивается с искомым (ключом). Если оно меньше, дальнейший поиск для возрастающего массива выполняется слева от центрального элемента. В противном случае ключ ищется справа.
- В случае совпадения среднего значения с искомым поиск прекращается. Пользователю возвращается индекс совпавшего элемента.
- Дальнейшие итерации первых двух шагов повторяются вплоть до нахождения ключа.
- Если в результате очередного деления остался лишь один элемент, и он не совпадает с искомым, пользователю возвращается значение -1.
Для большей наглядности рассмотрим пример из реальной практики.
Многие программисты задаются вопросом, почему в таком методе нельзя просто отсекать половину массива при поиске ключа. Рассмотрим такую ситуацию.
- Имеется массив данных: 1, 3, 6, 7, 13, 15, 16, 19, 24, 28, 29.
- Нужно найти элемент со значением 19.
- Центральный элемент равен 15.
- Поскольку число 19 больше 15, дальнейший поиск выполняется в правой половине.
- Таким образом, значение 19 ищется в новом массиве: 16, 19, 24, 28, 29.
входят в ТОП-30 с доходом
от 210 000 ₽/мес
Скачивайте и используйте уже сегодня:
Топ-30 самых востребованных и высокооплачиваемых профессий 2023
Поможет разобраться в актуальной ситуации на рынке труда
Подборка 50+ бесплатных нейросетей для упрощения работы и увеличения заработка
Только проверенные нейросети с доступом из России и свободным использованием
ТОП-100 площадок для поиска работы от GeekBrains
Список проверенных ресурсов реальных вакансий с доходом от 210 000 ₽
Последовательность действий во время второй и последующих итераций до обнаружения ключа:
- Серединой нового множества является число 24.
- Поскольку 19 меньше 24, работа выполняется в левой половине данного массива.
- Новая последовательность содержит всего пару чисел — 16 и 19.
- Так как 19 больше 16, обрабатывать нужно элементы правее.
- А справа находится лишь одно значение, которое равно искомому — 19.
- Таким образом, ключ найден.
Мы привели простой пример, содержащий небольшое число шагов до обнаружения искомого элемента. Итого, за 4 итерации удалось обнаружить ключ в последовательности из 11 чисел.
Реализация бинарного поиска в программировании
Алгоритм двоичного поиска сравнительно легко реализуется на языке Си. Простейшая программа может иметь примерно такой код:
int bin_find(int n, int *x, long A)
{
int m, left, right;
left = 0; right = n-1;
while (true)
{
if (left > right) return (-1); // ключ не найден
m = left + (right — left) / 2;
if (x[m] < A) left = m + 1;
if (x[m] > A) right = m — 1;
if (x[m] == A) return m;
}
}
В данном случае три индексные переменные lk, mk, rk сгруппированы в одну, так как в алгоритме используются лишь последнее значение числового ряда.
Реализация последовательного алгоритма двоичного поиска
Если поиск требуемого элемента не увенчался успехом, пользователю, как правило, возвращается значение -1. Но могут встречаться и другие варианты вывода, зависящие от условий использования метода:
- «Магическое число»
В данном случае выводится значение, вывод которого в случае успешного поиска невозможен. Например, алгоритм возвращает результат вычисления (lk+1). Здесь k — это номер шага, выполняемого перед тем, как будет нарушено условие lk < rk. Таким образом пользователю будет передаваться информация о предполагаемом местонахождении ключа. Этот результат в дальнейшем может быть использован, к примеру, для вставки нового элемента в найденное место множества, оставляя массив упорядоченным.
Скачать файл- Специальная константа
Назначается конкретным языком программирования. В частности, C# содержит константу null и требует использования типа «int?» для результата вместо стандартного «int». Аналогом в Python является «…».
- Исключение
Возвращается в случае невозможной работы, если искомый элемент не найден, хотя должен иметься в массиве.
Несмотря на сравнительную простоту исходного кода, в нем все же могут возникнуть ловушки. Поэтому их следует учитывать:
- Первая и последняя переменные массива по отдельности вмещаются в максимальный размер типа данных, а их сумма уже выходит за разрешенные пределы.
В теории массивы такого большого размера могут возникать. При этом программистам приходится внедрять конструкции вида «first + (last — first) / 2», гарантированно не приводящим к переполнению. Здесь первая и последняя переменная должны быть неотрицательными целыми числами.
- Упомянутые элементы first и last являются указателями либо итераторами.
В таком случае приведенный выше код будет единственно корректным. Если преобразовать его в uintptr_t и провести последующий расчет, это нарушит абстракцию. При этом корректный результат не будет гарантирован. Для сохранения сложности алгоритма необходимо внедрять быстрые операции «итератор+число → итератор», «итератор−итератор → число».
- Первый и последний элементы массива имеют тип данных со знаком.
Расчет производится с переводом в беззнаковый тип: ((unsigned)first + (unsigned)last) / 2. На языке Java это будет иметь вид: (first + last) >>> 1.
- Требуется выполнить расчет на ассемблере, используя флаг переноса.
Используется конструкция вида add eax, b; rcr eax, 1. Но для длинных типов данных более целесообразным вариантом будет first + (last — first) / 2.
на обучение «Аналитик больших данных» до 28 апреля
В процессе бинарного поиска элементов довольно часто случаются ошибки на единицу. По этой причине особую важность имеет предварительное тестирование подобных случаев. Например, в пустом массиве производится поиск отсутствующего значения (слишком большого, слишком малого и среднего). Также ищутся крайние элементы множества. Далее проверяют, не вышел ли алгоритм за границы массива и не попал ли он в бесконечный цикл.
Иногда множество содержит несколько экземпляров искомого элемента и нужно найти, например, самый первый (последний) экземпляр или даже следующий за первым (или последним) экземпляром элемент.
Ученый Йон Бентли заметил, что 9 из 10 начинающих разработчиков, создавая алгоритм двоичного поиска, попросту не берут в расчет указанные выше особенности. Даже код самого Бентли, опубликованный в качестве примера в нескольких учебных изданиях, обладает недостатком, связанным с возможным переполнением.
ТОП-100 площадок для поиска работы от GeekBrains
20 профессий 2023 года, с доходом от 150 000 рублей
Чек-лист «Как успешно пройти собеседование»
Реализация параллельного алгоритма двоичного поиска
Алгоритм можно модифицировать внедрением p-ого поиска, позволяющего заранее задавать любое количество процессоров (p). В таком случае множество делится на p+1 частей, а не пополам. Все новые узлы при этом вычисляются и сравниваются с ключом независимо друг от друга (параллельно). Примерная высота ЯПФ определяется по формуле K=lg(p)+1n.
Реализовывать алгоритм двоичного поиска для архитектур с разделенной памятью в любом случае бессмысленно. Нелокальный доступ к исходным данным, а также сравнительно малое число вычислительных операций даже в условиях распараллеливания сводят всю эффективность на нет, так как извлекаемая выгода будет поглощаться коммуникациями.
В теории целесообразно использовать системы с общей памятью путем внедрения OpenMP. Но чтобы получить хотя бы какой-то выигрыш в скорости, необходимо выполнить ряд условий:
- В память помещается весь массив исходных данных.
- Программа начинает работу с однократного статического создания нитей.
Существенная же выгода распараллеливания будет возможна при условии многократного поиска в данном массиве. При этом внутри одной параллельной секции должно осуществляться хотя бы 1000 операций (или примерно 30 поисков в массиве из миллиарда элементов).
Проблемы бинарного поиска
Получив полное представление об особенностях алгоритма поиска и рассмотрев характерные примеры, можно приступать к реализации этого алгоритма с использованием какого-нибудь языка программирования. Это упражнение займет немного времени и будет весьма полезным даже для опытных разработчиков.
Сложность бинарного поиска, несмотря на сравнительную простоту его алгоритма, заключается в самой практической реализации. Здесь полезно привести слова упомянутого выше Йона Бентли, которые он адресовал своим студентам:
Многие программисты убеждены, что лишь обладая полноценным описанием алгоритма двоичного поиска, они способны легко написать для этого алгоритма программу. Но это является заблуждением. Попробуйте самостоятельно реализовать поиск в виде кода и убедитесь, что эта задача — не из легких.
Итак, алгоритм бинарного поиска по своей сути простой, но при этом правильно реализовать его достаточно сложно. В книге Дональда Кнута «Sorting and Searching» говорится о первой публикации идеи двоичного поиска. Впервые принцип был опубликован в 1946 году, но лишь спустя 12 лет этот принцип грамотно реализовали в виде кода программы.
По заверению Йона Бентли подобную задачу он задавал не только своим студентам, но и профессиональным разработчикам. Как уже упоминалось, лишь десятая часть начинающих и опытных программистов с первого раза справлялась с заданием. Курьез заключается в том, что собственный код Бентли содержит ошибки. И по сей день подобные ошибки обнаружить весьма непросто.
Рассмотренные примеры показывают принцип работы бинарного дерева поиска. Алгоритм реализуется практически во всех известных языках программирования. Он эффективен в большинстве случаев при грамотной реализации, но для его нормального функционирования необходимо заранее отсортировать массив нужным образом.
Разберем 11 самых важных жизненных вопросов
Только до 
Эксклюзивные лекции по основам программирования
