Теория: Бинарный поиск

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

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

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

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

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

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

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

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

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

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

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

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

Упорядочим города по году основания, и тогда ответ будет очевиден:

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

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

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

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

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

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

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

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

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

Javascript

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;
}

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. Мы вставили сюда слова из нашей таблицы, но, чтобы код не получился слишком большим, ограничились десятком слов.

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

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

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

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

Бинарный поиск — это метод поиска, при котором алгоритм ищет элементы в ограниченной области поиска, причем с каждым шагом область поиска делится на две части.

Кратко опишем механизм работы бинарного поиска:

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

Теперь посмотрим, как выглядит бинарный поиск в нашем примере со стоп-словами.

Алгоритм начинается с середины — это слово «который».

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

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

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

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

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

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

Как реализовать бинарный поиск

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

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

Javascript

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

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

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

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

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

        if ($candidate < STOP_WORDS[$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;
    }
}

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

Javascript

// индекс первого элемента области поиска
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.

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

Javascript

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.

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

Javascript

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

Python

middle = (first + last) // 2

PHP

$middle = floor(($first + $last) / 2);

Java

// В Java для целых чисел используется целочисленное деление
var middle = (first + last) / 2;

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

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

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

Javascript

last = middle

Python

last = middle

PHP

<?php

$last = $middle;

Java

last = middle;

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

Javascript

last = middle - 1

Python

last = middle - 1

PHP

<?php

$last = $middle - 1;

Java

last = middle - 1;

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

Javascript

first = middle + 1

Python

first = middle + 1

PHP

<?php

$first = $middle + 1;

Java

first = middle + 1;

Мы сократили область поиска вдвое, а теперь надо повторить предыдущие шаги — тогда в нашей программе появится цикл:

Javascript

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 = floor(($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.

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

Javascript

last = middle - 1

Python

last = middle - 1

PHP

<?php

$last = $middle - 1;

Java

last = middle - 1;

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

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

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

Javascript

first = middle + 1

Python

first = middle + 1

PHP

<?php

$first = $middle + 1;

Java

first = middle + 1;

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

Javascript

// пока область поиска не пуста
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.

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

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

Заключение

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