Модуль bisect — реализация алгоритма бинарного поиска. Бинарный поиск в питоне.

В этом руководстве мы обсудим, что такое бинарные квесты и как они работают. Мы рассмотрим пример бинарного квеста в Python, чтобы вы могли научиться писать такие квесты в своих программах. Давайте начнем!

Python binary search and linear search

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

Пример:

def binary_searchiter(arr, n): low = 0 high = len(arr) - 1 mid = 0 while low n: high = mid - 1 else: return mid retur n-1 arr = 4, 7, 9, 16, 20, 25 n = 7 r = binary_searchiter(arr, n) if r != -1: print("Элемент найден в индексе", str(r)) else: print("Элемент отсутствует в таблице")

После написания приведенного выше кода (бинарный поиск в Python без рекурсии) выводится Ones, и результат выглядит как «Item found at index 1» Здесь используется итерационный метод для нахождения номера в списке.

На следующем снимке экрана показан бинарный поиск в Python без рекурсии.

Python recursive binary search

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

Пример:

def binary_search(arr, low, high, number): if high>= low: mid = (high + low) // 2 if arrmid == number: return mid elif arrmid>number: return binary_search(arr, low, mid-1, number) else: return binary_search(arr, mid+1, high, number) else: retur n-1 arr = 5, 12, 17, 19, 22, 30 number = 22 r = binary_search(arr, 0, len(arr)-1, number) if r != -1: print("Элемент найден в индексе", str(r)) else: print("Элемент отсутствует в таблице")

После написания приведенного выше кода (рекурсивный бинарный поиск Python), Ones будет напечатан, а вывод будет выглядеть как «Item found at index 4». Здесь мы используем рекурсивный метод и передаем два новых параметра в функцию binary_search.

Вы можете увидеть рекурсивный бинарный поиск в Python на следующем снимке экрана.

Python binary search using a library find the first occurrence of an element

В данном случае мы будем использовать библиотечную функцию для выполнения двоичного поиска. Нам нужно вставить » from bisect import bisect_left «, и функция bisect.bisect_left(a, n) будет использоваться для возврата точки вставки n в крайнем левом углу отсортированного списка.

Пример:

from bisect import bisect_left def Binary_Search(a, n): i = bisect_left(a, n) if i != len(a) and ai == n: return i else: retur n-1 a = 2, 5, 5, 6, 10 n = int(5) val = Binary_Search(a, n) if val == -1: print(n, "не существует") else: print("первое вхождение", n, "присутствует в", val)

После написания приведенного выше кода (бинарный поиск Python с библиотекой find first occurrence of an element), после печати вывод выглядит как «First occurrence of 5 is present at 1» Здесь функция bisect_left() возвращает первое вхождение элемента в списке.

На следующем рисунке вы можете увидеть, где впервые встречается элемент

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

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

Сложность алгоритма составляет O(log n), но отсортированный список в Python имеет сложность O(n), вы должны иметь это в виду.

Реализация в модуле bisect

bisect.insort(list, elem, lo=0, hi=len(a)), или bisect.insort_right (list, elem, lo=0, hi=len(a)) — вставляет элемент в упорядоченный список, располагая его как можно дальше вправо (все равные ему элементы остаются слева). Параметры lo и hi (здесь и в других функциях) могут быть использованы для указания подмножества списка, которое должно быть включено; по умолчанию используется весь список.

bisect.insort_left(list, elem, lo=0, hi=len(a)) — Вставляет элемент в отсортированный список, располагая его как можно дальше слева (все равные элементы остаются справа).

bisect.bisect(list, elem, lo=0, hi=len(a)), или bisect.bisect_right (list, elem, lo=0, hi=len(a)) — Находит место для вставки элемента в отсортированный список, размещая elem как можно дальше справа.

bisect.bisect_left(list, elem, lo=0, hi=len(a)) — Находит позицию, в которой элемент вставляется в отсортированный список так, чтобы elem располагался как можно дальше слева.

Примеры

Функция, проверяющая, находится ли элемент в списке (аналогично elem в l ):

Чтобы вставить код Python в комментарий, заключите его в теги




Книги о Python
GUI (графический интерфейс пользователя)
Курсы Python
Модули
Новости мира Python
NumPy
Обработка данных
Основы программирования
Примеры программ
Типы данных в Python
Видео
Python для Web
Работа для Python-программистов

Итерационный бинарный поиск в Python
Во-первых, мы реализуем бинарный поиск с помощью итерационного метода. Мы будем перебирать набор утверждений и выполнять итерации над каждым элементом списка. Мы будем находить среднее значение до тех пор, пока поиск не будет завершен.
Вычислим следующую программу итерационного метода.
# Итеративный метод двоичного поиска Метод реализации функции Python # Возвращает индекс n в данном списке1, если он существует, # иначе возвращае т-1 def binary_search(list1, n): low = 0 high = len(list1) - 1 mid = 0 while low n: high = mid - 1 # Если n меньше, чем слева от mid else: return mid # элемента не было в списке, retur n-1 retur n-1 # исходный list1 list1 = 12, 24, 32, 39, 45, 50, 54 n = 45 # вызов функции result = binary_search(list1, n) if result ! = -1: print("Элемент существует в индексе", str(result)) else: print("Элемент не существует в списке1")
Пункт существует в индексе 4
В приведенной выше программе:

Мы создали функцию под названием binary_search(), которая принимает два аргумента – список для сортировки и число для поиска.
Мы объявили две переменные для хранения наименьшего и наибольшего значений в списке. Начальное значение low присваивается 0, high – len (list1) – 1, а mid – 0.
Затем мы объявили цикл while с условием, что наименьшее значение равно и меньше наибольшего. Цикл while будет повторяться, если число еще не найдено.
В цикле while мы находим среднее значение и сравниваем значение индекса с искомым числом.
Если значение среднего индекса меньше n, мы увеличиваем среднее значение на 1 и присваиваем ему значение. Поиск перемещается влево.
В противном случае уменьшите среднее значение и назначьте его максимальному. Поиск переместится в правую сторону.
Если n равно среднему значению, верните mid.
Это будет происходить до тех пор, пока минимум не станет равным и меньше максимума.
Если мы дойдем до конца функции, значит, элемента нет в списке. Возвращаем -1 вызывающей функции.

Рассмотрим рекурсивную процедуру двоичного поиска.
Рекурсивный двоичный поиск
В двоичном поиске мы можем использовать рекурсию. В данном случае мы определим рекурсивную функцию, которая будет вызывать сама себя до тех пор, пока не будет выполнено условие.
# Python программа для рекурсивного двоичного поиска. # def binary_search(list1, low, high, n): # Проверка базового случая для рекурсивной функции if low n: return binary_search(list1, low, mid - 1, n) # Иначе поиск переходит к правому подсписку1 else: return binary_search(list1, mid + 1, high, n) else: # Запись не существует в list1 retur n-1 # Test list1ay list1 = 12, 24, 32, 39, 45, 50, 54 n = 32 # Вызов функции res = binary_search(list1, 0, len(list1)-1, n) if res ! = -1: print("Элемент существует в индексе", str(res)) else: print("Элемент не существует в списке1")
Пункт существует в индексе 2
Приведенная выше программа аналогична предыдущей. Мы объявляем рекурсивную функцию и ее базовое условие. Условием является то, что меньшее значение меньше или равно большему значению.

Среднее число вычисляем как в прошлой программе.
Мы используем оператор if, чтобы продолжить двоичный поиск.
Если среднее значение равно числу, которое мы ищем, возвращается среднее значение.
Если среднее значение меньше значения, мы снова ищем нашу рекурсивную функцию binary_search(), увеличиваем среднее значение на единицу и присваиваем низкое значение.
Если среднее значение больше, чем значение, которое мы ищем, тогда наша рекурсивная функция binary_search() снова уменьшит среднее значение на единицу и присвоит ему низкое.

В предыдущей части мы написали нашу основную программу. Это та же программа, что и предыдущая, за исключением того, что мы передали два параметра в функцию binary_search().
Это связано с тем, что мы не можем присвоить рекурсивной функции начальные значения для низких, высоких и средних значений. При каждом вызове рекурсивного метода значение этих переменных будет обнуляться. Это приведет к неправильному результату.
Сложность
Сложность алгоритма двоичного поиска в лучшем случае составляет O(1). Это происходит в том случае, если искомый элемент найден в первом сравнении. O (logn) - наихудшая и средняя сложность бинарного поиска, она зависит от количества переборов, выполняемых для нахождения искомого элемента.
Мы рассмотрели оба метода для нахождения положения индекса заданного числа. Алгоритм бинарного поиска - это самый эффективный и быстрый способ найти элемент в списке. Он пропускает ненужные сравнения. Как следует из названия, поиск разделен на две части. Он фокусируется на той стороне списка, которая ближе всего к искомому номеру.