Метод двух указателей python

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

Заключение

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

Источник

Метод двух указателей в Python

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

Базовый принцип

Основная идея метода двух указателей заключается в том, чтобы использовать два указателя (обычно именуемых левый и правый), которые перемещаются по массиву или списку. Эти указатели обычно начинают с противоположных концов массива и двигаются в сторону друг друга, проверяя определенные условия, связанные с задачей. В процессе выполнения алгоритма указатели могут перемещаться в одном или обоих направлениях, а также могут останавливаться на определенных позициях.

Пример: поиск пары чисел с заданной суммой

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

def find_pair_with_sum(arr, target_sum): left, right = 0, len(arr) - 1 while left < right: current_sum = arr[left] + arr[right] if current_sum == target_sum: return (arr[left], arr[right]) elif current_sum < target_sum: left += 1 else: right -= 1 return None

Пример: длина минимального подмассива с заданной суммой

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

def min_subarray_length(arr, target_sum): left, right = 0, 0 current_sum = 0 min_length = float("inf") while right < len(arr): current_sum += arr[right] while current_sum >= target_sum: min_length = min(min_length, right - left + 1) current_sum -= arr[left] left += 1 right += 1 return min_length if min_length != float("inf") else 0

Заключение

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

Источник

Метод двух указателей

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

Петя решил купить статуэтки всех видов от 1 до k. Оказалось, что Петя получит приличную скидку, если купит статуэтки, стоящие не в произвольных местах, а некоторым непрерывным отрезком (все статуэтки от какой-то позиции l до r включительно). Петя сразу понял, что ему может потребоваться купить несколько статуэток одного вида, повторяющиеся он решил подарить друзьям после возвращения домой.

Например, если в лавке статуэтки выставлены в порядке 1 2 2 3 3 1, и Петя хочет купить статуэтки видов от 1 до 3, то он может купить статуэтки с первой по четвертую позиции (при этом будут куплены две статуэтки вида 2). Если же в лавке выставлены статуэтки 1 2 5 4 3 (вновь k=3), то Петя купит все 5 статуэток.

Помогите определить Пете минимальную суммарную стоимость статуэток, расположенных подряд в лавке, чтобы среди них были статуэтки всех видов от 1 до k.

Гарантируется, что для всех тестовых данных ответ существует.

В первой строке записаны два целых числа n и k (1≤k≤n≤500000).

Во второй сроке записаны n целых чисел ai (вид i-й статуэтки) (1≤ai≤n) — описания статуэток в сувенирной лавке. Статуэтки перечислены слева направо.

Гарантируется, что для всех тестовых данных ответ существует.

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

Ввод:
6 3
1 2 2 3 3 1
Вывод: 8

Ввод: 5 3
1 2 5 4 3
Вывод: 15

Ввод: 6 3
1 2 6 3 3 1
Вывод: 12

Ввод: 6 1
6 2 3 1 2 3
Вывод: 1

Ввод: 7 7
1 2 3 4 6 5 7
Вывод: 28

Ввод:
10 2
1 9 2 4 3 1 8 2 10 9
Вывод: 10

Источник