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

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

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

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

В этом уроке мы познакомимся с двумя алгоритмами — методом перебора и бинарным поиском.

Метод перебора

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

Начнем с самого простого алгоритма перебора — поиска по списку.

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

А вот слова «а» и «на» встречаются в огромном количестве других запросов и в самых разных предложениях. На результаты поиска они не влияют, потому что поисковые машины исключают их из запроса.

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

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

или

вас

для

после

ого

раньше

но

ее

на

во

эх

позже

дабы

что

по

не

браво

когда-то

затем

который

со

же

здравствуйте

очень

потом

их

из

то

спасибо

минимально

лишь

все

от

бы

извините

максимально

только

они

до

всего

что-то

а

он

я

без

итого

какой-то

огромный

мы

весь

над

даже

где-то

предельно

его

мне

под

да

как-то

сильно

вы

меня

за

нет

дальше

слабо

вам

таким

при

ой

ближе

самый

Сейчас таблица неудобная — в ней нет какого-либо порядка. Чтобы найти нужное слово, придется постоянно просматривать весь список, тратить время и силы. Работа пойдет быстрее и проще, если упорядочить слова по алфавиту. Слова упорядочены по колонкам:

а

где-то

здравствуйте

меня

он

самый

без

да

из

минимально

они

сильно

ближе

дабы

извините

мне

от

слабо

браво

даже

или

мы

очень

со

бы

дальше

итого

на

по

спасибо

вам

для

их

над

под

таким

вас

до

как-то

не

позже

то

весь

его

какой-то

нет

после

только

во

ее

когда-то

но

потом

что

все

же

который

ого

предельно

что-то

всего

за

лишь

огромный

при

эх

вы

затем

максимально

ой

раньше

я

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

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

Будапешт

Эти два примера показывают нам два варианта поиска по списку:

  • В примере со стоп-словами мы проверяли, есть ли слово в списке. Это самый простой вид поиска

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

По обоим примерам видно, насколько медленно работает метод перебора. В худшем случае алгоритму придется проверить практически все значения в списке.

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

Чтобы не тратить так много времени на авторизацию в Facebook и работу с другими массивами, можно использовать более быстрый алгоритм.

Как ускорить алгоритм перебора

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

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

Чтобы это сделать, начнем с простого метода перебора:

const stopWords = ['ее', 'на', 'по', 'со', 'же', 'браво', 'всего', 'я', 'итого'];

const isStopWord = (candidate) => {
  for (let i = 0; i < stopWords.length; i += 1) {
    if (stopWords[i] === candidate) {
      return true;
    }
  }

  return false;
};
Python
stop_words = ['ее', 'на', 'по', 'со', 'же', 'браво', 'всего', 'я', 'итого']

def is_stop_word(stop_words, candidate):
    for i in range(len(stop_words)):
        if stop_words[i] == candidate:
            return True
    return False
PHP
<?php

$stopWords = ['ее', 'на', 'по', 'со', 'же', 'браво', 'всего', 'я', 'итого'];

function isStopWord($stopWords, $candidate)
{
  foreach ($stopWords as $word) {
    if ($word === $candidate) {
      return true;
    }
  }

  return false;
}
Java
class App {

    private static List<String> stopWords = List.of(
        "ее", "на", "по", "со", "же", "браво", "всего", "я", "итого"
    );

    public static boolean isStopWord(String candidate) {
        for(String word : stopWords) {
            if (word.equals(candidate)) {
                return true;
            }
        }

        return false;
    }
}

Функция isStopWord() перебирает слова-кандидаты, последовательно сравнивает их с каждой строкой в массиве стоп-слов и возвращает true или 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;
};
Python
stop_words = ['а', 'без', 'ближе', 'браво', 'бы', 'вам', 'вас', 'весь', 'во', 'все', 'всего', 'вы']

def is_stop_word(stop_words, candidate):
    # индекс первого элемента области поиска
    first = 0
    # индекс последнего элемента области поиска
    last = len(stop_words) - 1

    while (first <= last):
        # индекс среднего элемента области поиска
        middle = (first + last) // 2

        if candidate == stop_words[middle]:
            # если нашли слово-кандидат, поиск завершается удачно
            return True

        if candidate < stop_words[middle]:
            # если кандидат меньше, отбрасываем правую половину
            last = middle - 1
        else:
            # если кандидат больше, отбрасываем левую половину
            first = middle + 1

    return False
PHP
<?php

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

function isStopWord($candidate)
{
    $first = 0;
    $last = count($stopWords) - 1;

    while ($first <= $last) {
        $middle = round(($first + $last) / 2);

        if ($candidate === $stopWords[$middle]) {
            return true;
        }

        if ($candidate < $stopWords[$middle]) {
            $last = $middle - 1;
        } else {
            $first = $middle + 1;
        }
    }

    return false;
};
Java
class App {

    private static List<String> stopWords = List.of(
        "а", "без", "ближе", "браво", "бы", "вам", "вас", "весь", "во", "все", "всего", "вы"
    );

    public static boolean isStopWord(String candidate) {
        // индекс первого элемента области поиска
        var first = 0;
        // индекс последнего элемента области поиска
        var last = stopWords.size() - 1;

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

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

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

        return false;
    }
}

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

// индекс первого элемента области поиска
let first = 0;
// индекс последнего элемента области поиска
let last = stopWords.length - 1;
Python
# индекс первого элемента области поиска
first = 0
# индекс последнего элемента области поиска
last = len(stop_words) - 1
PHP
<?php

$first = 0;
$last = count(stopWords) - 1;
Java
// индекс первого элемента области поиска
var first = 0;
// индекс последнего элемента области поиска
var last = stopWords.size() - 1;

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

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

const middle = (first + last) / 2;
Python
middle = (first + last) / 2
PHP
<?php

$middle = ($first + $last) / 2
Java
var middle = (first + last) / 2;

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

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

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

// индекс среднего элемента области поиска
const middle = Math.floor((first + last) / 2);
Python
middle = (first + last) // 2
PHP
$middle = round(($first + $last) / 2);
Java
// В Java для целых чисел используется целочисленное деление
var middle = (first + last) / 2;

Дальше есть три варианта развития событий.

Вариант 1: Слово-кандидат может совпадать со средним словом — поиск завершен с положительным результатом.

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

last = middle;
Python
last = middle
PHP
<?php

$last = $middle;
Java
last = middle;

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

last = middle - 1;
Python
last = middle - 1
PHP
<?php

$last = $middle - 1;
Java
last = middle - 1;

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

first = middle + 1;
Python
last = middle + 1
PHP
<?php

$last = $middle + 1;
Java
last = 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;
  }
}
Python
while (???):
    # индекс среднего элемента области поиска
    middle = (first + last) // 2

    if candidate == stop_words[middle]:
        # если нашли слово-кандидат, поиск завершается удачно
        return True

    if candidate < stop_words[middle]:
        # если кандидат меньше, отбрасываем правую половину
        last = middle - 1
    else:
        # если кандидат больше, отбрасываем левую половину
        first = middle + 1
PHP
<?php

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

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

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

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

    if (candidate.compareTo(stopWords.get(middle)) < 0) {
        // если кандидат меньше, отбрасываем правую половину
        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;
Python
last = middle - 1
PHP
<?php

$last = $middle - 1;
Java
last = middle - 1;

Мы помним, что значения first, last и middle совпадают, так что новое значение last окажется на единицу меньше first. Ситуация кажется странной — как последнее слово может находиться перед первым?

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

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

first = middle + 1;
Python
first = middle + 1
PHP
<?php

$first = $middle + 1;
Java
last = middle + 1;

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

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

return false;
Python
# пока область поиска не пуста
while first <= last:
    # ...

return False
PHP
<?php

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

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

Недостатки бинарного поиска

На примере списка стоп-слов сравним метод перебора и бинарный поиск. Первое заметное отличие — бинарный поиск сложнее в реализации. В нашем случае сортировка метода перебора занимает 8 строк, а бинарный поиск — 18 строк. Стоит ли писать такие сложные программы? Да, если мы ищем по массиву из ста элементов и более.

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

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

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

И третье ограничение — некоторые данные просто нельзя упорядочить. Например, не существует какого-то естественного общепризнанного способа упорядочить цвета:

Цвета

Таким же образом, сложно упорядочить пары чисел. Возьмем для примера широту и долготу — это как раз пара чисел:

  • Самый западный город России — Балтийск, его координаты 54°39′ с. ш. 19°55′ в. д.

  • Самый северный — Певек, координаты 69°42′ с. ш. 170°19′ в. д.

Какие координаты больше? Если бы речь шла только о широте или долготе, мы бы без труда ответили. Но здесь пара чисел: при сравнении широта может оказаться больше, а долгота меньше. Нельзя сказать, что широта важнее долготы или наоборот. Поэтому у координат и других пар чисел нет какого-то естественного и очевидного порядка.

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

Преимущества бинарного поиска

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

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

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

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

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

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

Лучшим для бинарного поиска также окажется один цикл. В худшем случае бинарный поиск пройдет четыре цикла:

  • Первый поиск — целый массив из 10 элементов

  • Второй — подмассив из пяти элементов

  • Третий — подмассив из двух элементов

  • Четвертый — подмассив с одним последним элементом

В итоге среднее число циклов для бинарного поиска — 2.

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

Размер Перебор, среднее Бинарный поиск, среднее

10

5

2

1 000

500

5

1 000 000

500 000

10

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

Заключение

  • В уроке мы рассмотрели два алгоритма: метод перебора и бинарный поиск

  • У метода перебора есть два варианта:

    • Простой перебор, чтобы проверить, есть ли элемент в списке

    • Поиск по ключу, если нужно найти элемент по одному атрибуту

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

  • Бинарный поиск гораздо быстрее обычного поиска, но при этом сложнее в реализации


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

  1. Бинарный поиск
  2. Статья «Сравнение производительности метода перебора и бинарного поиска»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»