Двоичный поиск python пример

Двоичный, или бинарный, поиск элемента

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

При решении задачи на языке программирования Python вместо массива используется список

Описание алгоритма

1. Находится средний элемент последовательности. Для этого первый и последний индексы связываются с переменными, а индекс среднего элемента вычисляется.
2. Значение среднего элемента сравнивается с искомым значением. Если значение среднего элемента оказывается равным искомому, поиск завершается.
3. Иначе, в зависимости от того, искомое значение больше или меньше значения среднего элемента, дальнейший поиск будет происходить только в левой или только в правой половинах массива.
4. Для этого одна из границ исследуемой последовательности сдвигается. Если искомое значение больше значения среднего элемента, то нижняя граница сдвигается за средний элемент на один элемент справа. Если искомое значение меньше значения среднего элемента, то верхняя граница сдвигается на элемент перед средним.
5. Снова находится средний элемент теперь уже в выбранной половине. Описанный выше алгоритм повторяется для данного среза.

Исходный код на Python

from random import randint # Создание списка, # его сортировка по возрастанию # и вывод на экран a = [] for i in range(10): a.append(randint(1, 50)) a.sort() print(a) # искомое число value = int(input()) mid = len(a) // 2 low = 0 high = len(a) - 1 while a[mid] != value and low  high: if value > a[mid]: low = mid + 1 else: high = mid - 1 mid = (low + high) // 2 if low > high: print("No value") else: print("ID =", mid)

[6, 17, 21, 27, 32, 35, 35, 36, 37, 48] 27 ID = 3

[4, 5, 12, 13, 13, 18, 22, 26, 30, 35] 28 No value

Другие варианты решения задачи двоичного поиска на Python:

from random import randint a = [randint(1, 50) for i in range(10)] a.sort() print(a) value = int(input()) left = 0 right = len(a) - 1 center = (left + right) // 2 while a[center] != value: if value > a[center]: left = center + 1 else: right = center - 1 center = (left + right) // 2 if left >= right: break if value == a[center]: print("ID =", center) else: print("No value") 

from random import randint a = [randint(1, 50) for i in range(10)] a.sort() print(a) value = int(input()) left = 0 right = len(a) - 1 while left  right: center = (left + right) // 2 if value == a[center]: print("ID =", center) break if value > a[center]: left = center + 1 else: right = center - 1 else: print("No value") 

Источник

Двоичный поиск в 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) – это наихудшая и средняя сложность двоичного поиска, зависит от количества выполняемых поисков, чтобы найти элемент, который мы ищем.

Заключение

Мы обсудили оба метода, чтобы найти позицию индекса данного числа. Алгоритм двоичного поиска – самый эффективный и быстрый способ поиска элемента в списке. Он пропускает ненужное сравнение. Как следует из названия, поиск разделен на две части. Он фокусируется на той стороне списка, которая близка к номеру, который мы ищем.

Источник