Приближенный двоичный поиск python

Введение в алгоритмы. Реализация на языке Python. Модуль 10. Бинарный поиск.

Бинарный поиск — это метод решения задач, который основан на делении пополам.

Одним из примеров бинарного поиска служит поиск слова в словаре. Пусть у нас есть англо-русский словарь и требуется найти перевод какого-то слова. Откроем словарь где-то в середине и сравним слово, написанное на открытой странице, с искомым словом. Если это слово идёт лексикографически раньше, чем искомое слово, то искомое слово надо искать во второй половине словаря, а иначе его надо искать в первой половине словаря. Таким образом, за один шаг мы сократили диапазон поиска с целого словаря до половины словаря. Аналогично поступим на втором шаге — откроем такую страницу словаря, которая делит половину словаря, в которой находится искомое слово, на две равные части, и сравним написанное там слово с искомым словом. После второго шага мы сократим диапазон поиска до четверти словаря. И так далее, будем поступать аналогичным образом, каждый раз сокращая искомый диапазон страниц в два раза, пока он не сократится до одной страницы, на которой находится искомое слово.

Так как каждый раз диапазон поиска сокращается в два раза, то искомая страница будет найдена за O(log n) шагов. Стоит отметить, что если на каждом шаге середина будет найдена не совсем точно, то диапазон поиска может сокращаться менее чем в два раза за один шаг, но асимптотика от этого не изменится.

Другой пример применения бинарного поиска это игра в угадывание числа. Пусть нам загадали натуральное число от 1 до N. Мы должны отгадать это число, задавая вопросы вида: «Верно ли, что загаданное число меньше X?», где X — некоторое натуральное число. Желательно использовать как можно меньше вопросов. Используя бинарный поиск, можно отгадать число за O(log n) вопросов. Для этого сначала зададим вопрос для X≈N/2 чтобы вне зависимости от полученного ответа сократить диапазон поиска примерно в два раза. И будем поступать так на каждом шаге, если на текущий момент мы знаем что наше число находится в диапазоне от L до R, то будем задавать вопрос для X≈(R+L)/2.

Например, если N=16 и нам загадали число 10, то мы сначала спросим: «Верно ли, что загаданное число меньше 9?». Нам ответят, что это неверно, и наш диапазон поиска сократится до чисел от 9 до 16. Затем мы спросим: «Верно ли, что загаданное число меньше 13?». Нам ответят, что это верно, и диапазон поиска сократиться до чисел от 9 до 12. Затем мы спросим: «Верно ли, что загаданное число меньше 11?». Нам ответят, что это верно, и диапазон поиска сократится до чисел от 9 до 10. Наконец мы спросим: «Верно ли, что загаданное число меньше 10?». Нам ответят, что это неверно, и мы узнаем, что загаданное число равно 10.

Чтобы написать бинарный поиск для решения задачи, будем опираться на подход, который использует понятие инварианта. Любая задача на бинпоиск сводится к тому, что некоторое условие выполнено для всех натуральных (или целых) индексов до какого-то значения, а после этого значения условие не выполнено для всех индексов. И задача состоит в том, чтобы найти либо последний индекс ,для которого условие выполнено, либо первый индекс, для которого условие не выполнено. Сначала необходимо найти целые индексы L и R такие, что для индекса L условие выполнено, а для индекса R условие не выполнено — это правило для индексов L и R сохраняется на всех шагах алгоритма и называется инвариантом. Далее на каждом шаге алгоритма бинарного поиска мы будем брать число в середине отрезка [L,R], которое можно вычислить по формуле M= ⌊( R+L)/2 ⌋ . Если условие для индекса M выполнено, то мы можем левую границу бинарного поиска сдвинуть в M, тем самым перейдя от отрезка [L,R] к отрезку [M,R]. Если же условие для индекса M не выполнено, то мы можем правую границу бинарного поиска сдвинуть в M, тем самым перейдя от отрезка [L,R] к отрезку [L,M]. В любом случае наш отрезок сократиться примерно в два раза, что нам и требуется. Алгоритм бинарного поиска будет выполняться до тех пор, пока границы поиска L и R не станут двумя соседними числами. А так как при выполнении нашего алгоритма мы сохраняли инвариант, то на последнем шаге индекс L будет последним индексом, для которого условие выполнено, а индекс R будет первым индексом, для которого условие не выполнено.

Рассмотрим типичную реализацию алгоритма бинарного поиска на языке Python. Пусть некоторое условие выполнено для L = 0 и не выполнено для R = 100. Тогда код бинарного поиска можно реализовать следующим образом.

R = 100 while R — L > 1 :

if ( ok ( M )) : L = M else :

При этом где-то выше должна быть реализована функция ok, которая получает целый индекс и возвращает True, если условие задачи для этого индекса выполнено, и False в противном случае.

Бинарный поиск в массиве

Рассмотрим задачу о поиске заданного числа в отсортированном массиве. Пусть заданы число x и отсортированный массив a₀≤a₁≤…≤a_n−1. Требуется найти, на какой позиции в массиве стоит число x, либо определить, что такого числа в массиве нет. Сначала добавим в наш массив два фиктивных элемента — элемент -∞ с индексом −1 и элемент +∞ с индексом n. Получим массив:

Тогда мы можем выбрать следующие границы бинпоиска: L=−1, R=n, потому что на позиции −1 стоит число заведомо меньшее, чем число x, а на позиции n стоит число заведомо большее, чем число x.

Далее мы можем выбрать один из двух инвариантов для решения нашей задачи.

После того как алгоритм бинарного поиска с таким инвариантом закончит свою работу и индексы L и R окажутся соседними числами, то число x надо искать на позиции с индексом L. Если L=−1, то это будет означать, что числа x нет в массиве. Если L≥0 и a[L]≠x, то числа x нет в массиве. Если же L≥0 и a[L]=x, то число x найдено на позиции с индексом L. Причём, если в массиве есть несколько элементов равных числу x, то индекс L задаёт позицию последнего вхождения числа x в массив. Таким образом, при данном инварианте индекс R будет задавать позицию, которая следует после последнего вхождения числа x, то есть верхнюю границу вхождений числа x, и поэтому такой индекс R принято называть UpperBound.

Для решения задач достаточно одного из двух предложенных инвариантов. Но бывает удобно использовать эти инварианты в паре. Например, если нам необходимо найти количество чисел в нашем массиве, для которых выполнено условие l≤ai≤r, то их количество можно найти по формуле UpperBound(r)−LowerBound(l). Удобство этой формулы в том, что она работает верно во всех случаях.

Приведём код на языке Python, который реализует бинарный поиск числа x в отсортированном массиве a с использованием инварианта 1.

L = — 1 R = n while R — L > 1 : M = ( R + L ) // 2

Lower bound

На вход подаются N целых чисел, а также набор из M запросов, каждый из которых — целое число. Ваша задача — для каждого запроса найти количество чисел из исходного набора, меньших заданного в запросе числа. Использовать встроенные функции бинарного поиска запрещено.

Входные данные Первая строка содержит число N — количество элементов в массиве. 1≤N≤250000.

Вторая строка содержит N целых чисел A_i через пробел. −10 9 ≤Ai≤10 9 . Третья строка содержит число M — количество запросов. 1≤M≤250000. Четвёртая строка содержит M целых чисел Q_i через пробел. −10 9 ≤Q_i≤10 9 .

Выходные данные

Выведите единственную строку с M целыми числами — количествами чисел исходного массива, меньших соответствующему запросу.

Примеры

Upper bound

На вход подаются N целых чисел, а также набор из M запросов, каждый из которых — целое число. Ваша задача — для каждого запроса найти количество чисел из исходного набора, меньших либо равных заданному в запросе числу. Использовать встроенные функции бинарного поиска запрещено.

Входные данные

Первая строка содержит число N — количество элементов в массиве. 1≤N≤250000.

Вторая строка содержит N целых чисел A_i через пробел. −10 9 ≤Ai≤10 9 . Третья строка содержит число M — количество запросов. 1≤M≤250000. Четвёртая строка содержит M целых чисел Q_i через пробел. −10 9 ≤Q_i≤10 9 .

Выходные данные

Выведите единственную строку с M целыми числами — количествами чисел исходного массива, меньших либо равных соответствующему запросу.

Примеры

a = sorted ( list ( map ( int , input ().split()))) M = int ( input ())

b = list ( map ( int , input ().split())) answers = list () for x in b: L = — 1 R = n while R — L > 1 : M = (R + L) // 2 if a[M]

Приближённый двоичный поиск

Для каждого из K чисел найдите ближайшее к нему число в отсортированном массиве.

Входные данные

Выходные данные

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

Примеры

n , k = map ( int , input ().split())

a = list ( map ( int , input ().split())) b = list ( map ( int , input ().split()))

for i in b: L = 0 R = n — 1 while R — L > 1 : M = (R + L) // 2 if a[M] < i: L = M else : R = M if i - a[L]

Сложность двоичного поиска

Вася загадал число от 1 до N. За какое наименьшее количество вопросов (на которые Вася отвечает «да» или «нет») Петя может заведомо угадать Васино число?

Вводится одно натуральное число N, не превосходящее 10000.

Выходные данные

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

from math import ceil , log2

print (ceil(log2( int ( input ()))))

Встроенный бинарный поиск

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

from bisect import *

Есть две функции, которые реализуют поиск нижней и верхней границы для числа x — bisect_left и bisect_right. Также есть функция bisect, которая делает то же самое, что и функция bisect_right. Эти функции можно применять на отсортированном списке.

Пусть нам, к примеру, дан следующий список: a = [1, 2, 2, 3, 5]

Тогда если мы посчитаем нижнюю границу для числа 2 в этом списке как bisect_left(a, 2), то мы получим, что этот индекс равен числу 1. Если же посчитаем верхнюю границу для числа 2 как bisect_right(a, 2), то получим в качестве ответа число 3. Индекс 1 указывает на позицию первого вхождения числа 2 в данный список, а индекс 3 указывает на позицию, которая идёт сразу за последним вхождением числа 2.

Функции bisect, bisect_left и bisect_right реализуют алгоритм бинарного поиска в отсортированном списке и работают за O(log n).

В данной задаче можно пользоваться встроенными функциями.

Входные данные

Выходные данные

Требуется для каждого из K чисел вывести в отдельную строку «YES», если это число встречается в первом массиве, и «NO» в противном случае.

Примеры

def binary_search (listt , item):

mid = int ((low + high) / 2 ) guess = listt[mid] if guess == item: return mid if guess > item: high = mid — 1 else : low = mid + 1 return None

n , k = map ( int , input ().split()) lstn = list ( map ( int , input ().split())) lstk = list ( map ( int , input ().split())) for ans in lstk: if binary_search(lstn , ans) is None :

Левый и правый двоичный поиск

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

Входные данные

В первой строке входных данных записаны два числа N и M (1≤N,M≤20000). Во второй строке записаны N упорядоченных по неубыванию целых чисел — элементы первого списка. В третьей строке записаны M целых неотрицательных чисел — элементы второго списка. Все числа в списках — целые 32-битные знаковые.

Выходные данные

Программа должна вывести M строчек. Для каждого числа из второго списка нужно вывести номер его первого и последнего вхождения в первый список. Нумерация начинается с единицы. Если число не входит в первый список, нужно вывести одно число 0.

N , M = map ( int , input ().split()) list1 = [ int (x) for x in input ().split()] list2 = [ int (x) for x in input ().split()]

i = bisect.bisect_left(list1 , x) if i >= N: print ( 0 ) continue if list1[i] == x:

print (i + 1 , bisect.bisect(list1 , x , i)) else :

Треугольники

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

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

Два отрезка считаются различными, если различаются их номера в порядке ввода.

Входные данные

В первой строке записано число n, 3 ≤ n ≤ 1000.

В следующих строках записаны длины отрезков 1≤a_i≤10 9 .

Вывести одно число — количество треугольников.

Примеры

n = int ( input ()) a = [] s = 0 for _ in range (n):

a.sort() for i in range (n — 1 ): for j in range (i + 1 , n): min_ = abs (a[i] — a[j]) max_ = (a[i] + a[j]) ri = bisect_right(a , min_) ra = bisect_right(a , max_) while ra > 0 and a[ra — 1 ] == max_:

Источник