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