Бесплатный доступ к вебинару Как стать специалистом по внедрению ИИ
Получить доступ бесплатно
ГлавнаяБлогБинарный поиск: зачем нужен и как реализовать
Бинарный поиск
5 285
Время чтения: 14 минут

Бинарный поиск: зачем нужен и как реализовать

5 285
Время чтения: 14 минут
Сохранить статью:
Сохранить статью:

О чем речь? Бинарный поиск – это алгоритм поиска элемента в отсортированном массиве данных. Этот метод является довольно популярным в программировании и может быть реализован на разных языках: от С до Python.

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

В статье рассказывается:

  1. Понятие бинарного поиска
  2. Принцип работы бинарного поиска на примере
  3. Реализация бинарного поиска в программировании
  4. Проблемы бинарного поиска
  5. Пройди тест и узнай, какая сфера тебе подходит:
    айти, дизайн или маркетинг.
    Бесплатно от Geekbrains

Понятие бинарного поиска

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

Понятие бинарного поиска
Понятие бинарного поиска

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

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

Принцип работы бинарного поиска на примере

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

  1. Вычисляется среднее значение массива.
  2. Значение полученного элемента сравнивается с искомым (ключом). Если оно меньше, дальнейший поиск для возрастающего массива выполняется слева от центрального элемента. В противном случае ключ ищется справа.
  3. В случае совпадения среднего значения с искомым поиск прекращается. Пользователю возвращается индекс совпавшего элемента.
  4. Дальнейшие итерации первых двух шагов повторяются вплоть до нахождения ключа.
  5. Если в результате очередного деления остался лишь один элемент, и он не совпадает с искомым, пользователю возвращается значение -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 ₽/мес
Павел Симонов - исполнительный директор Geekbrains
Павел Симонов
Исполнительный директор Geekbrains
Команда GeekBrains совместно с международными специалистами по развитию карьеры подготовили материалы, которые помогут вам начать путь к профессии мечты.
Подборка содержит только самые востребованные и высокооплачиваемые специальности и направления в IT-сфере. 86% наших учеников с помощью данных материалов определились с карьерной целью на ближайшее будущее!

Скачивайте и используйте уже сегодня:

Павел Симонов - исполнительный директор Geekbrains
Павел Симонов
Исполнительный директор Geekbrains
pdf иконка

Топ-30 самых востребованных и высокооплачиваемых профессий 2023

Поможет разобраться в актуальной ситуации на рынке труда

doc иконка

Подборка 50+ бесплатных нейросетей для упрощения работы и увеличения заработка

Только проверенные нейросети с доступом из России и свободным использованием

pdf иконка

ТОП-100 площадок для поиска работы от GeekBrains

Список проверенных ресурсов реальных вакансий с доходом от 210 000 ₽

pdf 3,7mb
doc 1,7mb
Уже скачали 26812 pdf иконка

Последовательность действий во время второй и последующих итераций до обнаружения ключа:

  • Серединой нового множества является число 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.

Дарим скидку от 60%
на обучение «Аналитик больших данных» до 10 марта
Уже через 9 месяцев сможете устроиться на работу с доходом от 150 000 рублей
Забронировать скидку

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

Расчет на ассемблере
Расчет на ассемблере

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

Ученый Йон Бентли заметил, что 9 из 10 начинающих разработчиков, создавая алгоритм двоичного поиска, попросту не берут в расчет указанные выше особенности. Даже код самого Бентли, опубликованный в качестве примера в нескольких учебных изданиях, обладает недостатком, связанным с возможным переполнением.

Только до 7.03
Скачай подборку материалов, чтобы гарантированно найти работу в IT за 14 дней
Список документов:
ТОП-100 площадок для поиска работы от GeekBrains
20 профессий 2023 года, с доходом от 150 000 рублей
Чек-лист «Как успешно пройти собеседование»
Чтобы получить файл, укажите e-mail:
Введите e-mail, чтобы получить доступ к документам
Подтвердите, что вы не робот,
указав номер телефона:
Введите телефон, чтобы получить доступ к документам
Уже скачали 52300

Реализация параллельного алгоритма двоичного поиска

Алгоритм можно модифицировать внедрением p-ого поиска, позволяющего заранее задавать любое количество процессоров (p). В таком случае множество делится на p+1 частей, а не пополам. Все новые узлы при этом вычисляются и сравниваются с ключом независимо друг от друга (параллельно). Примерная высота ЯПФ определяется по формуле K=lg(p)+1n.

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

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

В теории целесообразно использовать системы с общей памятью путем внедрения OpenMP. Но чтобы получить хотя бы какой-то выигрыш в скорости, необходимо выполнить ряд условий:

  • В память помещается весь массив исходных данных.
  • Программа начинает работу с однократного статического создания нитей.
Реализация параллельного алгоритма двоичного поиска
Реализация параллельного алгоритма двоичного поиска

Существенная же выгода распараллеливания будет возможна при условии многократного поиска в данном массиве. При этом внутри одной параллельной секции должно осуществляться хотя бы 1000 операций (или примерно 30 поисков в массиве из миллиарда элементов).

Проблемы бинарного поиска

Получив полное представление об особенностях алгоритма поиска и рассмотрев характерные примеры, можно приступать к реализации этого алгоритма с использованием какого-нибудь языка программирования. Это упражнение займет немного времени и будет весьма полезным даже для опытных разработчиков.

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

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

Привлекает мир кодирования и создания программ? На курсе программиста с нуля до Junior вы освоите основы, познакомитесь с языками и инструментами разработки, и станете готовы к созданию своих первых проектов в IT-индустрии.

Итак, алгоритм бинарного поиска по своей сути простой, но при этом правильно реализовать его достаточно сложно. В книге Дональда Кнута «Sorting and Searching» говорится о первой публикации идеи двоичного поиска. Впервые принцип был опубликован в 1946 году, но лишь спустя 12 лет этот принцип грамотно реализовали в виде кода программы.

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

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

Рассмотренные примеры показывают принцип работы бинарного дерева поиска. Алгоритм реализуется практически во всех известных языках программирования. Он эффективен в большинстве случаев при грамотной реализации, но для его нормального функционирования необходимо заранее отсортировать массив нужным образом.

Оцените статью
Рейтинг: 2.67
( голосов 3 )
Поделиться статьей
Добавить комментарий

Сортировать:
По дате публикации
По рейтингу
До конца акции осталось
0 дней 00:00:00
Дарим скидку 64% на обучение «Разработчик»
  • Получите новую профессию с гарантией трудоустройства
  • Начните учиться бесплатно, 3 месяца обучения в подарок
Забронировать скидку на обучение
Забрать подарок

Получите подробную стратегию для новичков на 2023 год, как с нуля выйти на доход 200 000 ₽ за 7 месяцев

Подарки от Geekbrains из закрытой базы:
Осталось 17 мест

Поздравляем!
Вы выиграли 4 курса по IT-профессиям.
Дождитесь звонка нашего менеджера для уточнения деталей

Иван Степанин
Иван Степанин печатает ...