Все, что вам нужно знать об алгоритме бинарного поиска

Освойте алгоритм бинарного поиска за 8 минут

Как бы вы искали слово в словаре английского языка? Я знаю, как вы бы этого не сделали: начните с первой страницы и просматривайте каждое слово, пока не найдете то, что искали — если, конечно, ваше слово не «трубкозуб». Но если бы вы искали слово «зоопарк», этот подход занял бы много времени.

Как бы вы искали слово в словаре английского языка?

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

Этот подход представляет собой расплывчатое описание алгоритма двоичного поиска, который находит положение элемента в отсортированном списке элементов. Он называется бинарным поиском (от латинского bīnī: «два на два, пара»), потому что он делит массив на две половины на каждой итерации, чтобы сузить область поиска.

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

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

Алгоритм

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

Постановка задачи

На Leetcode, платформе для практики написания вопросов для интервью, проблема бинарного поиска формулируется следующим образом [3]:

Имея отсортированный (в порядке возрастания) целочисленный массив nums из n элементов и значение target, напишите функцию для поиска target в nums. Если цель существует, вернуть ее индекс; в противном случае вернуть -1.

Вход: отсортированный массив (nums) и целевое значение (target)
Вывод: индекс значения target

Алгоритм бинарного поиска

Алгоритм бинарного поиска работает следующим образом:

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

Прохождение с примером

Давайте рассмотрим алгоритм бинарного поиска на примере. На изображении ниже вы можете увидеть отсортированный массив nums = [3, 7, 8, 9, 14, 16, 17, 22, 24] с n = 9 элементами. Мы хотим найти положение target = 8.

Итерация 1:

Мы определяем пространство поиска его начальным и конечным индексами, называемыми low и high. Мы устанавливаем пространство поиска, назначая low индексу первого элемента в массиве (0) и high индексу последнего элемента в массиве (8).

Получаем индекс среднего элемента массива mid по формуле (low + high)//2. Эта операция выполняет функцию пола для достижения желаемого среднего элемента: mid = (low + high) // 2 = (0 + 8) / 2 = 4

Значение среднего элемента равно nums[mid] = nums[4] = 14 и, следовательно, больше target = 8. Таким образом, все элементы справа от среднего элемента могут быть отброшены. Мы вдвое уменьшаем пространство поиска, обновляя high до (mid — 1) = 4 — 1 = 3.

Итерация 2:

Теперь повторяем шаг 2.

Индекс среднего элемента массива теперь равен mid = (low + high) // 2 = (0 + 3) / 2 = 1. Значение среднего элемента равно nums[mid] = nums[1] = 7 и, следовательно, меньше, чем target = 8. Таким образом, все элементы слева от среднего элемента могут быть отброшены. Мы вдвое уменьшаем пространство поиска, обновляя low до (mid + 1) = 1 + 1 = 2.

Итерация 3:

Снова повторяем шаг 2.

Индекс среднего элемента массива теперь равен mid = (low + high) // 2 = (1 + 3) / 2 = 2.

Значение среднего элемента равно nums[mid] = nums[2] = 8 и, следовательно, равно target = 8. Мы возвращаем mid = 2 в качестве позиции цели и завершаем функцию.

Выполнение

В этом разделе вы увидите самую элементарную реализацию алгоритма бинарного поиска на Python и C++. Мы также рассмотрим встроенные функции бинарного поиска в Python и C++.

Существуют различные реализации алгоритма бинарного поиска [4]. Однако в этой статье будет обсуждаться только элементарная итеративная реализация, которая также является наиболее распространенной реализацией.

питон

Реализация Python выглядит так, как показано ниже:

Вместо написания собственной функции двоичного поиска вы можете использовать функцию bisect_left() из модуля bisect в Python [5].

from bisect import bisect_left
i = bisect_left(target, nums)

C++

Реализация C++ выглядит так, как показано ниже:

В C++ стандартная библиотека шаблонов (STL) предоставляет функцию lower_bound(), которую можно использовать, как показано в следующем примере [2]. Также есть функция binary_search(), которая возвращает логическое значение независимо от того, существует ли target в отсортированном массиве или нет, но не его позицию [1].

#include <algorithm>
i = std::lower_bound(nums.begin(), nums.end(), target);

Обсуждение

Алгоритм бинарного поиска имеет временную и пространственную сложность:

временная сложность является логарифмической с O(log n)[6]. Если n — длина входного массива, временная сложность алгоритма бинарного поиска в наихудшем случае равна O(log n), поскольку он выполняется путем деления пространства поиска вдвое на каждой итерации. Например, если бы мы хотели найти элемент в массиве длиной 8, в худшем случае потребовалось бы log₂(8) = 3 итерации.
пространственная сложность постоянна с O(1). Поскольку алгоритму требуется место для трех индексов, mid, low и high, но не требуется дополнительного места для каждой итерации.

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

Например, если бы мы хотели найти элемент в массиве из предыдущего примера длины восемь, в худшем случае потребовалось бы n = 8 итераций. Для алгоритма бинарного поиска потребуется всего три итерации.

Однако главный недостаток алгоритма бинарного поиска заключается в том, что он требует, чтобы отсортированный массив отбрасывал половину пространства поиска на каждой итерации. Хотя массив можно отсортировать до запуска алгоритма двоичного поиска, алгоритм сортировки увеличит общую временную сложность. В общем случае сортировка имеет временную сложность O(n log n), что хуже, чем линейная временная сложность алгоритма линейного поиска.

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

Заключение

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

Понимание алгоритма двоичного поиска может помочь вам писать более эффективные алгоритмы, независимо от того, являетесь ли вы инженером-программистом, специалистом по данным или кем-то еще

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

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

Понравилась эта история?

Если вы хотите получать мои новые истории прямо на свой почтовый ящик, подпишитесь!

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

Присоединяйтесь к Medium по моей реферальной ссылке — Леони Монигатти
Прочитайте все статьи Леони Монигатти (и тысяч других авторов на Medium). Ваш членский взнос напрямую…medium.com

Найди меня в Twitter, LinkedIn,и Kaggle!