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 – это алгоритм поиска определенного элемента в списке. Предположим, у нас есть список из тысяч элементов, и нужно получить индексную позицию определенного элемента. Мы можем очень быстро найти позицию индекса элемента, используя алгоритм двоичного поиска.
Существует множество поисковых алгоритмов, но наиболее популярным среди них является бинарный поиск.
Элементы в списке должны быть отсортированы для применения алгоритма двоичного поиска. Если элементы не отсортированы, сначала отсортируйте их. Давайте разберемся с концепцией бинарного поиска.
Концепция двоичного поиска
В алгоритме двоичного поиска мы можем найти позицию элемента, используя следующие методы:
Принцип «разделяй и властвуй» лежит в основе рекурсивного метода. В нем функция вызывается снова и снова, пока не найдет элемент в списке.
Набор операторов повторяется несколько раз, чтобы найти позицию индекса элемента в итеративном методе. Цикл while используется для выполнения этой задачи.
Двоичный поиск более эффективен, чем линейный поиск, потому что нам не нужно искать каждый индекс списка. Список должен быть отсортирован для выполнения алгоритма двоичного поиска.
Рассмотрим пошаговую реализацию бинарного поиска.
У нас есть отсортированный список элементов, и мы ищем позицию индекса 45.
Итак, мы устанавливаем два указателя в нашем списке. Один указатель используется для обозначения меньшего значения, называемого низким, а второй указатель используется для обозначения самого высокого значения, называемого высоким.
Далее мы вычисляем значение среднего элемента в массиве.
mid = (low+high)/2 Here, the low is 0 and the high is 7. mid = (0+7)/2 mid = 3 (Integer)
Теперь мы сравним искомый элемент со средним значением индекса. В этом случае 32 не равно 45. Поэтому нам нужно провести дальнейшее сравнение, чтобы найти элемент.
Если число, которое мы ищем, равно mid. Затем верните mid, иначе переходите к дальнейшему сравнению.
Число для поиска больше среднего числа, мы сравниваем n со средним элементом элементов справа от mid и устанавливаем low на low = mid + 1.
В противном случае сравните n со средним значением элементов слева от mid и установите high в high = mid – 1.
Повторяйте, пока не будет найден номер, который мы ищем.
Итерационный бинарный поиск в Python
Сначала мы реализуем двоичный поиск с итерационным методом. Мы будем повторять набор операторов и перебирать каждый элемент списка. Мы найдем среднее значение, пока поиск не завершится.
Разберемся в следующей программе итерационного метода.
# Iterative Binary Search Function method Python Implementation # It returns index of n in given list1 if present, # else returns -1 def binary_search(list1, n): low = 0 high = len(list1) - 1 mid = 0 while low n: high = mid - 1 # If n is smaller, compared to the left of mid else: return mid # element was not present in the list, return -1 return -1 # Initial list1 list1 = [12, 24, 32, 39, 45, 50, 54] n = 45 # Function call result = binary_search(list1, n) if result != -1: print("Element is present at index", str(result)) else: print("Element is not present in list1") Element is present at index 4
В приведенной выше программе:
- Мы создали функцию под названием binary_search(), которая принимает два аргумента – список для сортировки и число для поиска.
- Мы объявили две переменные для хранения наименьшего и наибольшего значений в списке. Начальное значение low присваивается 0, high – len (list1) – 1, а mid – 0.
- Затем мы объявили цикл while с условием, что наименьшее значение равно и меньше наибольшего. Цикл while будет повторяться, если число еще не найдено.
- В цикле while мы находим среднее значение и сравниваем значение индекса с искомым числом.
- Если значение среднего индекса меньше n, мы увеличиваем среднее значение на 1 и присваиваем ему значение. Поиск перемещается влево.
- В противном случае уменьшите среднее значение и назначьте его максимальному. Поиск переместится в правую сторону.
- Если n равно среднему значению, верните mid.
- Это будет происходить до тех пор, пока минимум не станет равным и меньше максимума.
- Если мы дойдем до конца функции, значит, элемента нет в списке. Возвращаем -1 вызывающей функции.
Рассмотрим рекурсивный метод двоичного поиска.
Рекурсивный двоичный поиск
В бинарном поиске можно использовать метод рекурсии. В этом случае мы определим рекурсивную функцию, которая будет вызывать сама себя до тех пор, пока не выполнит условие.
# Python program for recursive binary search. # Returns index position of n in list1 if present, otherwise -1 def binary_search(list1, low, high, n): # Check base case for the recursive function if low n: return binary_search(list1, low, mid - 1, n) # Else the search moves to the right sublist1 else: return binary_search(list1, mid + 1, high, n) else: # Element is not available in the list1 return -1 # Test list1ay list1 = [12, 24, 32, 39, 45, 50, 54] n = 32 # Function call res = binary_search(list1, 0, len(list1)-1, n) if res != -1: print("Element is present at index", str(res)) else: print("Element is not present in list1") Element is present at index 2
Вышеупомянутая программа аналогична предыдущей. Мы объявили рекурсивную функцию и ее базовое условие. Условие: наименьшее значение меньше или равно наибольшему значению.
- Среднее число вычисляем как в прошлой программе.
- Мы используем оператор if, чтобы продолжить двоичный поиск.
- Если среднее значение равно числу, которое мы ищем, возвращается среднее значение.
- Если среднее значение меньше значения, мы снова ищем нашу рекурсивную функцию binary_search(), увеличиваем среднее значение на единицу и присваиваем низкое значение.
- Если среднее значение больше, чем значение, которое мы ищем, тогда наша рекурсивная функция binary_search() снова уменьшит среднее значение на единицу и присвоит ему низкое.
В последней части мы написали нашу основную программу. Это то же самое, что и предыдущая программа, но с той лишь разницей, что мы передали два параметра в функцию binary_search().
Это потому, что мы не можем присвоить начальные значения low, high и mid в рекурсивной функции. Каждый раз, когда вызывается рекурсивный метод, значение этих переменных сбрасывается. Это даст неправильный результат.
Сложность
Сложность алгоритма двоичного поиска в лучшем случае составляет O (1). Это произойдет, если элемент, который мы ищем, найден при первом сравнении. O (logn) – это наихудшая и средняя сложность двоичного поиска, зависит от количества выполняемых поисков, чтобы найти элемент, который мы ищем.
Заключение
Мы обсудили оба метода, чтобы найти позицию индекса данного числа. Алгоритм двоичного поиска – самый эффективный и быстрый способ поиска элемента в списке. Он пропускает ненужное сравнение. Как следует из названия, поиск разделен на две части. Он фокусируется на той стороне списка, которая близка к номеру, который мы ищем.