Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

Бинарный поиск Основы алгоритмов и структур данных

Бинарный поиск

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

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

Стоп-слова

Представим, что мы ищем в Яндексе или Google страницы, содержащие фразу «а роза упала на лапу Азора». Слова «роза», «упала», «лапа» встречаются только в этой фразе и поэтому значимы для поиска. Слова «а» и «на» встречаются очень часто и в самых разных предложениях, поэтому не влияют на результаты поиска.

Такие слова называются шумовыми или стоп-словами. К ним относятся союзы, частицы, предлоги, междометия и некоторые другие части речи. Поисковые машины исключают их из запроса. Фразу «а роза упала на лапу Азора» Яндекс и Google превращают в «роза упала лапу Азора».

У поисковой машины есть список стоп-слов, которые она должна исключить из текста. Давайте попробуем сделать эту работу вручную. Вот наш список стоп-слов.

иливасдляпослеогораньше
ноеёнавоэхпозже
дабычтопонебравокогда-то
затемкоторыйсожездравствуйтеочень
потомихизтоспасибоминимально
лишьвсеотбыизвинитемаксимально
толькоонидовсегочто-тоа
онябезитогокакой-тоогромный
мывесьнаддажегде-топредельно
егомнеподдакак-тосильно
выменязанетдальшеслабо
вамтакимприойближесамый

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

Двоичная система выглядит очень непривычно и числа, записанные в двоичной системе, получаются огромными. Зачем она вообще нужна? Разве компьютеры не могут работать с привычной нам десятичной системой? Оказывается, когда-то именно так они и работали. Самый первый компьютер ENIAC, разработанный в 1945 году, хранил числа в десятичной системе счисления. Для хранения одной цифры применялась схема, которая называется кольцевым регистром, состоящая из десяти радиоламп. Для хранения чисел от одного до миллиона нужно было 60 ламп.

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

агде-тоздравствуйтеменяонсамый
бездаизминимальноонисильно
ближедабыизвинитемнеотслабо
браводажеилимыоченьсо
быдальшеитогонапоспасибо
вамдляихнадподтаким
васдокак-тонепозжето
весьегокакой-тонетпослетолько
воеёкогда-тонопотомчто
всежекоторыйогопредельночто-то
всегозалишьогромныйприэх
вызатеммаксимальноойраньшея

Теперь работа идёт быстрее. Нам проще проверить, есть ли слово в списке, потому что стоп-слова упорядочены.

Европейские столицы

Приведённый нами пример довольно простой — нам надо узнать, встречается ли искомое слово в нашем списке. Кроме него существует чуть более сложный поиск по ключу. Ознакомимся с ним на примере с европейскими столицами. В таблице вы видите год основания и название столиц нескольких столиц. Дублин был основан в 1191 году, а Ватикан — в 752.

1804Вена1237Берлин1323Вильнюс
1614Тирана1167Копенгаген963Люксембург
1067Минск1191Дублин1275Амстердам
752Ватикан1786Рейкьявик1200Варшава
1872Будапешт856Мадрид1147Москва

Какой город основали в 1275 году? Для ответа на этот вопрос вам потребуется перебрать все записи в списке, потому что они расположены в случайном порядке. Упорядочим их по году основания.

752Ватикан1167Копенгаген1323Вильнюс
856Мадрид1191Дублин1614Тирана
963Люксембург1200Варшава1786Рейкьявик
1067Минск1237Берлин1804Вена
1147Москва1275Амстердам1872Будапешт

Теперь вы без труда ответите на вопрос.

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

Мы заметили, что поиск в списках, где слова или числа находятся без всякого порядка, очень долгий. Такой способ поиска называется последовательным поиском, линейным поиском или методом перебора. В худшем случае нам придётся проверить практически все значения в списке. Чтобы представить, насколько медленно это может работать, рассмотрим в качестве примера популярную социальную сеть Фейсбук, где на конец 2021 года были зарегистрированы 2,7 миллиарда человек. Каждый день они входят на сайт с помощью логина и пароля. А проверка логина и пароля — это уже знакомый нам поиск по атрибуту логин. Даже на самых быстрых современных компьютерах поиск в массиве из 2,7 миллиардов элементов занимает десятки секунд, даже минуты. Было бы очень грустно, если бы вход на Фейсбук занимал несколько минут.

Поэтому нам нужен быстрый алгоритм поиска.

Идея бинарного поиска

Мы без труда находим нужную информацию в справочниках и словарях — там, где словарные статьи упорядочены. Но если нас спросить, как мы это делаем, окажется, что рассказать об «алгоритме» не так просто. Часто люди обладают интуитивным знанием, но не могут его формализовать.

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

Чтобы это сделать, давайте начнём с простого метода перебора.

const stopWords = ['а', 'без', 'ближе', 'браво', 'бы', 'вам', 'вас', 'весь', 'во', 'все', 'всего', 'вы'];
/* Функция isStopWord() проверяет, является ли слово-кандидат стоп-словом.
 * Это простой вариант поиска, когда нам нужно узнать, есть ли слово в
 * списке, или нет, поэтому функция возвращает true или false.
 * Она последовательно сравнивает кандидата с каждой строкой в массиве
 * стоп-слов.
 */
const isStopWord = (candidate) => {
  for (let i = 0; i < stopWords.length; i += 1) {
    if (stopWords[i] === candidate) {
      return true;
    }
  }

  return false;
};

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

Другое дело упорядоченный массив. Если мы видим в середине списка слово «Который», то понимаем, что перед ним не может быть таких слов, как «Предельно» или «Чтобы», потому что буквы П и Ч в алфавите следуют за К. Если мы ищем слово «Очень», то можем отбросить все слова перед «Который», то есть, практически, половину нашего словаря!

Слово, которое мы ищем — в нашем случае слово «Очень» — называют кандидатом, ведь мы не можем гарантировать, что найдём его в массиве.

После того, как мы определили, что слово-кандидат может находиться только во второй половине списка, мы пропускаем соседние слова. Рядом с К находятся буквы Л и М, так что поблизости от «Который» могут быть лишь такие слова, как «Лишь» или «Мне». Буква О отстоит далеко, поэтому и слово «Очень” надо искать далеко. Так что заглядываем далеко вперёд и попадаем, скажем, на слово «Потом».

Ситуация со словом «Который» повторяется. Теперь О находится перед П, так что мы можем отбросить все слова после «Потом».

Если мы отбросим все слова перед «Который» и все слова после «Потом», в нашем распоряжении останется половина от половины первоначального списка, а именно — слова между «Который» и «Потом».

агде-тоздравствуйтеменяонсамый
бездаизминимальноонисильно
ближедабыизвинитемнеотслабо
браводажеилимыоченьсо
быдальшеитогонапоспасибо
вамдляихнадподтаким
васдокак-тонепозжето
весьегокакой-тонетпослетолько
воеёкогда-тонопотомчто
всежекоторыйогопредельночто-то
всегозалишьогромныйприэх
вызатеммаксимальноойраньшея

Это наша область поиска. В самом начале область поиска — весь список, но на каждом шаге она сокращается вдвое. Область поиска можно задать, указав её первое и последнее слова. В нашем примере на третьем шаге область поиска начинается со слова «Который» и продолжается до слова «Потом».

Алгоритм заканчивает работу, когда область поиска сужается до одного слова. Если это наше слово-кандидат, значит поиск завершился успешно.

Выделим ключевые момент и отличия от алгоритма последовательного поиска.

  • Последовательный поиск начинается с первого элемента в списке, а бинарный — со среднего.
  • На каждом шаге мы делим область поиска пополам. Область поиска задаётся первым и последним элементом. В самом начале, область поиска — это весь список.
  • Алгоритм завершается, когда область поиска сужается до одного элемента.

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

Реализация

Вот функция, которая проверяет наличие слова в отсортированном массиве стоп-слов.

const stopWords = ['а', 'без', 'ближе', 'браво', 'бы', 'вам', 'вас', 'весь', 'во', 'все', 'всего', 'вы'];

const isStopWord = (candidate) => {
  // индекс первого элемента области поиска
  let first = 0;
  // индекс последнего элемента области поиска
  let last = stopWords.length - 1;

  // пока область поиска не пуста
  while (first <= last) {
    // индекс среднего элемента области поиска
    const middle = Math.floor((first + last) / 2);

    if (candidate === stopWords[middle]) {
      // если нашли слово-кандидат, поиск завершается удачно
      return true;
    }

    if (candidate < stopWords[middle]) {
      // если кандидат меньше, отбрасываем правую половину
      last = middle - 1;
    } else {
      // если кандидат больше, отбрасываем левую половину
      first = middle + 1;
    }
  }

  return false;
};

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

// индекс первого элемента области поиска
let first = 0;
// индекс последнего элемента области поиска
let last = stopWords.length - 1;

First в переводе с английского означает первый, а last — последний. Мы помним, что элементы в массивах JavaScript нумеруются с нуля, поэтому сначала индекс первого элемента равен 0, а индекс последнего на единицу меньше длины массива. Чтобы убедиться в этом, представьте массив, например, из четырёх элементов: его элементы будут иметь индексы 0, 1, 2 и 3.

На каждом шаге мы сравниваем слово-кандидат со словом из середины области. Найти среднее слово не сложно: его индекс находится посередине между первым и последним словом.

const middle = (first + last) / 2;

В массиве с нечётным количеством элементов всё просто: у нас есть центральный элемент и две равные половины слева и справа от него. В массиве с чётным количеством элементов, длина левой и правой половин будет отличаться на единицу.

В нашей формуле это будет означать, что first + last не делится нацело на 2.

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

// индекс среднего элемента области поиска
const middle = Math.floor((first + last) / 2);

У нас есть три варианта развития событий. Во-первых, слово-кандидат может совпадать со средним словом. Это означает, что поиск завершён с положительным результатом. Во-вторых, слово-кандидат может быть меньше слова из середины, и это значит, что нам надо “отбросить” все элементы справа и продолжать поиск только в левой части. “Отбрасывание” означает, что на следующем шаге первое слово останется прежним, а последнее изменится. Последним словом в новой области поиска станет центральное слово из старой:

last = middle;

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

last = middle - 1;

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

first = middle + 1;

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

while (???) {
    // индекс среднего элемента области поиска
    const middle = Math.floor((first + last)/2);

    if (candidate === stopWords[middle]) {
      // если нашли слово-кандидат, поиск завершается удачно
      return true;
    }

    if (candidate < stopWords[middle]) {
      // если кандидат меньше, отбрасываем правую половину
      last = middle - 1;
    } else {
      // если кандидат больше, отбрасываем левую половину
      first = middle + 1;
    }
}

Мы пока не знаем условия завершения цикла, поэтому написали три знака вопроса. Чтобы разобраться с условием, обратим внимание, что на каждом шаге первое и последнее слово двигаются по направлению друг к другу и когда нибудь они совпадут. Тогда условие first === last станет истинным.

Если first === last, то формулу (first + last) / 2 можно записать и как (first + first) / 2, и как (last + last) / 2 — индекс центрального элемента в любом случае будет равен first и last.

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

last = middle - 1;

А мы помним, что значения first, last и middle совпадают, так что новое значение last окажется на единицу меньше first. Ситуация кажется странной — как вообще последнее слово может находится перед первым? Оказывается, так бывает, если речь идёт о вырожденных случаях. Область поиска стала пустой, в ней больше нет элементов для сравнения — это и есть вырожденный случай. При последнем сравнении слово-кандидат не совпало со словом из списка, значит, его вообще не было в списке.

Точно такая же ситуация возникнет, если слово-кандидат будет больше среднего слова, но там сработает вторая ветка

first = middle + 1;

Таким образом, цикл следует остановить, когда левая граница станет больше правой. Но в операторе while мы записываем не условие остановки цикла, а условие продолжения, поэтому условие надо поменять на обратное: first <= last. Если цикл завершается и кандидат в списке не найден, значит, поиск завершился неудачно и мы должны вернуть false.

  // пока область поиска не пуста
  while (first <= last) {
    
  }

  return false;

Мы рассмотрели все аспекты реализации и теперь можем собрать код воедино. У нас получится функция, которую мы видели в начале раздела.

Ограничения бинарного поиска

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

Да, стоит, если мы ищем данные в большом массиве. Если размер массива содержит больше ста элементов, имеет смысл применять бинарный поиск. (По ссылке вы можете ознакомиться со сравнением производительности линейного и бинарного поиска. Статья на английском языке.)

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

Вторым важным ограничением бинарного поиска является то, что массив с элементами должен быть упорядоченным. Стоп-слова — это фиксированный список, который надо подготовить один раз. Мы можем его упорядочить. А если список не фиксированный и надо добавлять слова во время работы программы, придётся писать дополнительный — и не самый простой — код. Мы не можем просто добавлять слова в конец массива, потому что это нарушит порядок.

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

Но нельзя в каком то разумном порядке расположить цвета.

Цвета

По крайней мере, нет очевидного способа. Точно также нет очевидного способа упорядочивать пары чисел.

Чтобы убедиться в этом, возьмём широту и долготу — это как раз пара чисел. Самый западный город России — Балтийск, его координаты 54°39′ с. ш. 19°55′ в. д. Самый северный — Певек, координаты 69°42′ с. ш. 170°19′ в. д. Какие координаты больше? Если бы речь шла об одном числе — широте или долготе, мы бы без труда ответили. Но здесь пара чисел. Может оказаться, что при сравнении широта окажется больше, а долгота меньше. Нельзя сказать, что широта важнее долготы или наоборот. Поэтому у координат нет какого-то естественного порядка.

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

Производительность

Мы говорили о том, что бинарный поиск быстрее метода перебора, но пока не обсудили, насколько именно он быстрее.

Один из способов сравнить производительность — написать программы и измерить время их выполнения. Это, так сказать, практический подход.

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

Давайте сравним время поиска на массивах из 10, 1 000 и 1 000 000 элементов.

Что мы будем сравнивать? В обоих алгоритмах у нас есть цикл. В одном случае он может выполняться 100 раз, а в другом 50, и это значит, что второй цикл в два раза быстрее первого, хотя мы и не можем назвать точное время в секундах.

Проблема в том, что на разных данных количество циклов будет разным.

В массиве из десяти элементов мы можем найти число с первого раза, а можем с десятого. В таких случаях принято считать среднее время выполнения, которое окажется где-то посередине. В среднем, в массиве из десяти элементов, метод перебора найдёт нужное число за пять циклов (10 делить на 2).

Лучшим для бинарного поиска также окажется один цикл. В худшем случае нам придётся разбивать массив из десяти элементов пополам несколько раз, пока у нас не получится один. Первый поиск мы делаем с целым массивом, второй — с подмассивом из пяти элементов, третий — с подмассивом из двух элементов, и, наконец, четвёртый — с одним последним элементом. Если худший случай это четыре цикла, то средний — два (4 делить на 2).

Сведём результаты в одну таблицу.

Размер Перебор, среднее Бинарный поиск, среднее
10 5 2
1 000 500 5
1 000 000 500 000 10

Как видим, разница в производительности и впрямь драматическая, особенно, на больших массивах.

Заключение

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

Дополнительные материалы

  1. Бинарный поиск

Аватары экспертов Хекслета

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты.

Ошибки, сложный материал, вопросы >
Нашли опечатку или неточность?

Выделите текст, нажмите ctrl + enter и отправьте его нам. В течение нескольких дней мы исправим ошибку или улучшим формулировку.

Что-то не получается или материал кажется сложным?

Загляните в раздел «Обсуждение»:

  • задайте вопрос. Вы быстрее справитесь с трудностями и прокачаете навык постановки правильных вопросов, что пригодится и в учёбе, и в работе программистом;
  • расскажите о своих впечатлениях. Если курс слишком сложный, подробный отзыв поможет нам сделать его лучше;
  • изучите вопросы других учеников и ответы на них. Это база знаний, которой можно и нужно пользоваться.

Об обучении на Хекслете

Для полного доступа к курсу нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
900
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.

  • 130 курсов, 2000+ часов теории
  • 900 практических заданий в браузере
  • 360 000 студентов
Даю согласие на обработку персональных данных, соглашаюсь с «Политикой конфиденциальности» и «Условиями оказания услуг»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff

Используйте Хекслет по максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Зарегистрируйтесь или войдите в свой аккаунт

Даю согласие на обработку персональных данных, соглашаюсь с «Политикой конфиденциальности» и «Условиями оказания услуг»