Предположим, вы ищете человека по имени «Винсент» в одном из этих больших телефонных справочников. Эти книги могут иметь сотни страниц, и было бы утомительно искать каждую страницу с самого начала линейным способом, пока вы не найдете этого человека. К счастью, книга отсортирована по алфавиту, так что мы можем использовать хак.
Представьте, что вы открываете книгу посередине. Вы смотрите на страницу и видите имена, начинающиеся с «S». Зная, что «V» стоит после «S», вы разрываете книгу пополам и выбрасываете половину книги с именами ниже «S». Теперь у вас осталась небольшая книга.
Затем вы снова открываете оставшуюся книгу наполовину. Вы смотрите туда, где вы приземлились, и видите имена, начинающиеся с «Х». Вы снова разрываете книгу пополам и выбрасываете половину с именами выше «X».
Продолжайте повторять эту процедуру, и достаточно скоро вы окажетесь на страницах, начинающихся с «V».
Это концепция бинарного поиска. Двоичный поиск — это эффективный алгоритм поиска значений в отсортированном массиве или списке. Он является частью большой категории алгоритмов под названием разделяй и властвуй. Эти классы алгоритмов берут сложную проблему и делят ее на более мелкие части подзадач, которые легче решить. Для бинарного поиска на каждом этапе решения задача каждый раз в основном уменьшается вдвое.
Чтобы проиллюстрировать процесс этого алгоритма, предположим, что мы хотим найти 89 в следующем упорядоченном массиве чисел. Нижняя и верхняя части диаграммы — это переменные, содержащие соответственно начальный и конечный индексы.
Начнем с вычисления среднего значения с использованием нижней и верхней переменных. Среднее значение равно 47, и это не то значение, которое нам нужно. Поскольку мы знаем, что 47 ‹ 89, мы можем исключить левую половину массива (все значения до 47 включительно). Это делается путем присвоения нижней переменной среднего индекса + 1. Размер нашей задачи уменьшился вдвое.
Процесс повторяется снова. Мы вычисляем среднее значение равным 97. Тогда мы знаем, что 97 > 89 и правую половину массива можно исключить из поиска, установив для верхней переменной средний индекс - 1.
Повторяем процесс снова. Среднее значение равно 89. Мы видим, что 89 = 89, поэтому мы можем остановить поиск и вернуть значение или индекс!
Линейный поиск занял бы у нас 7 шагов, но бинарный поиск занял бы у нас только 3 шага, чтобы найти 89. Для меньших массивов время вычислений между двумя алгоритмами будет незначительным. Однако для больших наборов данных — речь идет о миллионах значений — бинарный поиск более эффективен, чем линейный поиск.
Псевдокод
Шаги бинарного поиска можно записать так:
- Создайте переменную с именем «bottom», указывающую на нижнюю границу подмассива.
- Создайте переменную с именем «top», указывающую на верхнюю границу подмассива.
- Создайте переменную с именем «middle», чтобы указать на середину подмассива.
- Пока нижний ‹= верхний, сделайте следующее:
- Вычислить среднее значение
- Если среднее значение = целевое значение, вернуть индекс
- если среднее значение ‹ целевое значение, установить нижнее = среднее + 1
- Если среднее значение › целевое значение, установите верхнее значение = среднее -1
5. Целевое значение не существует в массиве
Визуальная демонстрация
Это небольшое приложение наглядно демонстрирует идею бинарного поиска. Целевое значение — это число, которое мы пытаемся угадать, а предположения, которые делает пользователь, — это среднее значение в нашем алгоритме бинарного поиска.
Репозиторий GitHub:
