10 812 subscribers

Введение в бинарный поиск

<100 full reads
Введение в бинарный поиск

Источник: Nuances of Programming

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

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

Затем вы снова открываете справочник на середине. Теперь вы видите имена, начинающиеся на букву “С”. Вы снова разрываете справочник пополам и выбрасываете ту половину, которая содержит имена до “С”.

Продолжайте повторять эту процедуру, и вскоре вы окажетесь на страницах с буквой “Э”.

Мы только что описали концепцию бинарного поиска. Это эффективный алгоритм поиска значений в отсортированном массиве или списке.

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

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

Введение в бинарный поиск

Начнем с вычисления среднего значения, используя нижнюю и верхнюю переменные. Среднее значение равно 47  —  это не то значение, которое нам нужно. Поскольку мы знаем, что 47 < 89, мы можем исключить левую половину массива (все значения до 47 включительно). Это делается путем присвоения нижней переменной среднего индекса +1 (middle index +1). Размер задачи уменьшился вдвое.

Введение в бинарный поиск

Процесс повторяется снова. Мы вычисляем, что среднее значение равно 97. Мы знаем, что 97 > 89, и правую половину массива можно исключить из поиска, присвоив верхней переменной средний индекс -1 (middle index -1).

Введение в бинарный поиск

Повторяем процесс еще раз. Среднее значение вычисляется равным 89. Мы видим, что 89 = 89, и поэтому можем прекратить поиск и вернуть значение/индекс!

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

Псевдокод

Этапы бинарного поиска можно описать следующим образом.

  1. Создание переменной bottom (нижней), указывающей на нижнюю границу подмассива.
  2. Создание переменной top (верхней), указывающей на верхнюю границу подмассива.
  3. Создание переменной middle (средней), указывающей на середину подмассива.
  4. Пока bottom остается <= top, нужно выполнить следующие действия.
  • Вычислить среднее значение.
  • Если среднее значение = целевому значению, вернуть индекс.
  • Если значение середины < целевого значения, установить bottom = middle +1.
  • Если среднее значение > целевого значения, установить top = middle -1.

5. Целевого значения нет в массиве.

Пример, реализованный в JS.

Визуальная демонстрация

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

Читайте также:

Читайте нас в Telegram, VK

Перевод статьи Xihai Luo: Introduction to Binary Search