Python. Бинарный поиск в массиве
В этой статье мы рассмотрим Двоичный (бинарный) поиск — один из классических алгоритмов поиска элемента в отсортированном массиве.
Предположим вы знаете в каком месяце родился ваш друг(пусть это будет сентябрь) , но не знаете в какой день. И вам нужно за наименьшее количество попыток определить в какой день месяца он родился. И при этом вам ваш друг на каждую вашу попытку будет давать один их трех ответов: «мало», «много» или «угадал»
Самый простой способ это метод простого поиска. Вы перебираете все варианты подряд 1, 2, 3 и далее.Конечно , если ваш друг родился 3 сентября вам понадятся всего лишь три попытки , но если 24 сентября , то вам нужно 24 попытки. А если друг родился 30 сентября , то нужны все 30 попыток.
Рассмотрим другой более эффективный метод поиска.
Допустим , что у нашего друга день рождения 24 сентября. Так как исходный массив содержит 30 элементов , то мы на первом шаге назовем элемент который находится посередине этого массива. Это число 15. Наш друг говорит , что «мало». И теперь мы понимаем , что все числа меньше 15 и само число 15 можно исключить из поиска и можно сосредоточиться на числах, которые больше 15.
На втором шаге мы назовем число которое находится посередине чисел от 16 до 30 и этим числом является 23 , но это тоже меньше искомого числа. И поэтому мы исключаем все числа меньше 23 и само число 23.
И так мы повторяем пока не найдем искомое число.В нашем случае это число 24.
Ниже на рисунке для наглядности показаны все шаги нахождения искомого числа(число 24) методом бинарного поиска
Чтобы найти число 24 в массиве из 30 элементов при помощи простого поиска нам нужно 24 попытки , то при помощи бинарного поиска нам потребовалось всего лишь 5 попыток. То есть в массиве из 30 элементов мы гарантированно за 5 попыток можем найти любой элемент, так log 30 примерно будет равно 5.
А что будет если у нас количество элементов равно не 30 , а скажем 1000? То тогда при простом поиске(переборе) , чтобы найти число 1000 нужно сделать 1000 итераций(попыток). А вот при бинарном поиске нужно сделать всего лишь 10 попыток , потому что 2 в 10 степени это 1024. Для 10 тысячи элементов при бинарном поиске нужно всего лишь 14 попыток , а вот при переборе количество попыток растет линейно. В этом и мощь бинарного алгоритма и его широкое распространение.
O(log n) — логарифмическая сложность для бинарного поиска
O(n) — Линейная сложность для простого поиска
Сравнение линейной и логарифмической функций.
Реализация алгоритма бинарного поиска на Python.
def binary_search(sequence, start_element, key): end_element = len(sequence) - 1 while start_element Заключение
В данной статье мы рассмотрели один из классических алгоритмов поиска. Это бинарный поиск элемента в отсортированном массиве.
Бинарный поиск в Python
В этом уроке мы рассмотрим бинарный поиск в Python, его идею, а также итеративную и рекурсивную реализацию.
Бинарный поиск в Python
Вступление
В этой статье мы погрузимся в идею и реализацию Python Binary Search .
Бинарный поиск-это эффективный алгоритм поиска, который работает с отсортированными массивами. Он часто используется как один из первых примеров алгоритмов, работающих в логарифмическом времени ( O(logn) ) из-за его интуитивного поведения и является фундаментальным алгоритмом в информатике.
Бинарный поиск – Пример
Бинарный поиск работает по принципу “разделяй и властвуй” и опирается на то, что массив сортируется так, чтобы исключить половину возможных кандидатов на каждой итерации. Более конкретно, он сравнивает средний элемент отсортированного массива с элементом, который он ищет, чтобы решить, где продолжить поиск.
Если целевой элемент больше среднего элемента – он не может быть расположен в первой половине коллекции, поэтому он отбрасывается. То же самое происходит и наоборот.
Примечание: Если массив имеет четное число элементов, то не имеет значения, с какого из двух “средних” элементов мы начнем.
Давайте быстро рассмотрим пример, прежде чем мы продолжим объяснять, как работает бинарный поиск:
Как мы видим, мы точно знаем, что, поскольку массив отсортирован, x не находится в первой половине исходного массива.
Когда мы знаем, в какой половине исходного массива находится x , мы можем повторить этот точный процесс с этой половиной и снова разделить ее на половинки, отбросив половину, которая наверняка не содержит x :
Мы повторяем этот процесс до тех пор, пока не получим подмассив, содержащий только один элемент. Мы проверяем, является ли этот элемент x . Если это так – мы нашли x , если это не так – x вообще не существует в массиве.
Если вы присмотритесь к этому поближе, то заметите, что в худшем случае ( x не существует в массиве) нам нужно проверить гораздо меньшее количество элементов , чем в несортированном массиве, что потребует чего-то большего в духе Линейного поиска , что безумно неэффективно.
Если быть более точным, то количество элементов, которые нам нужно проверить в худшем случае, равно log 2 N где N – количество элементов в массиве.
Это оказывает тем большее влияние, чем больше массив:
Если бы наш массив состоял из 10 элементов, нам нужно было бы проверить только 3 элемента, чтобы либо найти x , либо сделать вывод, что его там нет. Это 33,3%.
Однако, если бы в нашем массиве было 10 000 000 элементов, нам нужно было бы проверить только 24 элемента. Это 0,0002%.
Реализация Бинарного Поиска
Двоичный поиск-это естественно рекурсивный алгоритм, поскольку один и тот же процесс повторяется на все меньших и меньших массивах до тех пор, пока не будет найден массив размером 1. Однако, конечно, существует и итеративная реализация, и мы покажем оба подхода.
Рекурсивный
Давайте начнем с рекурсивной реализации, так как это более естественно:
def binary_search_recursive(array, element, start, end): if start > end: return -1 mid = (start + end) // 2 if element == array[mid]: return mid if element < array[mid]: return binary_search_recursive(array, element, start, mid-1) else: return binary_search_recursive(array, element, mid+1, end)
Давайте подробнее рассмотрим этот код. Мы выходим из рекурсии, если элемент start выше элемента end :
Это происходит потому, что такая ситуация возникает только тогда, когда элемент не существует в массиве. В результате мы получаем только один элемент в текущем суб-массиве, и этот элемент не совпадает с тем, который мы ищем.
В этот момент start равно end . Однако, поскольку element не равен array[mid] , мы снова “разбиваем” массив таким образом, что либо уменьшаем end на 1, либо увеличиваем start на единицу, и рекурсия существует при этом условии.
Мы могли бы сделать это, используя другой подход:
if len(array) == 1: if element == array[mid]: return mid else: return -1
Остальная часть кода выполняет логику “проверить средний элемент, продолжить поиск в соответствующей половине массива”. Мы находим индекс среднего элемента и проверяем, соответствует ли ему искомый элемент:
mid = (start + end) // 2 if elem == array[mid]: return mid
Если это не так, мы проверяем, является ли элемент меньше или больше среднего элемента:
Давайте продолжим и запустим этот алгоритм с небольшой модификацией, чтобы он распечатал, над каким подмассивом он работает в данный момент:
element = 18 array = [1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29] print("Searching for <>".format(element)) print("Index of <>: <>".format(element, binary_search_recursive(array, element, 0, len(array)))) Запуск этого кода приведет к:
Searching for 18 Subarray in step 0:[1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29] Subarray in step 1:[16, 18, 24, 28, 29] Subarray in step 2:[16, 18] Subarray in step 3:[18] Index of 18: 7
Ясно видеть, как он сокращает пространство поиска в каждой итерации, приближаясь все ближе и ближе к искомому элементу. Если бы мы попытались найти элемент, который не существует в массиве, результат был бы следующим:
Searching for 20 Subarray in step 0: [4, 14, 16, 17, 19, 21, 24, 28, 30, 35, 36, 38, 39, 40, 41, 43] Subarray in step 1: [4, 14, 16, 17, 19, 21, 24, 28] Subarray in step 2: [19, 21, 24, 28] Subarray in step 3: [19] Index of 20: -1
И просто для удовольствия мы можем попробовать поискать некоторые большие массивы и посмотреть, сколько шагов требуется двоичному поиску, чтобы выяснить, существует ли число:
Searching for 421, in an array with 200 elements Search finished in 6 steps. Index of 421: 169 Searching for 1800, in an array with 1500 elements Search finished in 11 steps. Index of 1800: -1 Searching for 3101, in an array with 3000 elements Search finished in 8 steps. Index of 3101: 1551
Повторяющийся
Итеративный подход очень прост и похож на рекурсивный. Здесь мы просто выполняем проверки в цикле while :
def binary_search_iterative(array, element): mid = 0 start = 0 end = len(array) step = 0 while (start : <>".format(step, str(array[start:end+1]))) step = step+1 mid = (start + end) // 2 if element == array[mid]: return mid if element < array[mid]: end = mid - 1 else: start = mid + 1 return -1
Давайте заполняем массив и ищем в нем элемент:
array = [1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29] print("Searching for <> in <>".format(element, array)) print("Index of <>: <>".format(element, binary_search_iterative(array, element))) Запуск этого кода дает нам результат:
Searching for 18 in [1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29] Subarray in step 0: [1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29] Subarray in step 1: [16, 18, 24, 28, 29] Subarray in step 2: [16, 18] Subarray in step 3: [18] Index of 18: 7
Вывод
Двоичный поиск-это невероятный алгоритм, который можно использовать на больших отсортированных массивах или всякий раз, когда мы планируем многократно искать элементы в одном массиве.
Стоимость сортировки массива один раз, а затем использования двоичного поиска для поиска элементов в нем несколько раз намного лучше, чем использование линейного поиска в несортированном массиве только для того, чтобы мы могли избежать затрат на его сортировку.
Если мы сортируем массив и ищем элемент только один раз, то более эффективно просто выполнить линейный поиск по несортированному массиву.
Если вы хотите прочитать об алгоритмах сортировки в Python , мы вас накроем!