[Из песочницы] Разбор задач. Бинпоиск_1
Здравствуйте, уважаемые хабровчане. Серия статей содержит разбор задач, которые дают на уроках информатике в Челябинском физико-математическом лицее №31. Немного истории… Наш лицей — одно из сильнейших учебных заведений России, который в рейтинге по конкурентоспособности выпускников занимает 5 место, уступив школам Москвы и Санкт-Петербурга. Ученики регулярно побеждают на олимпиадах всероссийского и международного уровня.
Так вот, перейдем к задачам. Эти задачи подразумевают собой использование бинарного поиска, в том числе бинпоиска по ответам. Как мы знаем бинпоиск — это алгоритм поиска объектов по заданному признаку в множестве объектов. Применяем для отсортированных по возрастанию/убыванию списков. Всего 4 задачи, 2 из которых направлены на применение «алгоритма без изюминок».
Левый и правый двоичный поиск
В этой задаче сначала нужно считать длины первой и второй строки, затем каждую следующую строку записать в список. После мы берем каждый элемент второго списка и ищем для него правую и левую границу. Можно заметить, что если число отсутствует в списке, итоговые значения левой границы и правой границы в левом и правом бинпоиске равны.
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
for x in b:
left = -1
right = len(a)
#левый бинпоиск, который ищет левую границу
while right - left > 1:
middle = (right + left) // 2
if a[middle] < x:
left = middle
else:
right = middle
left_1 = -1
right_1 = len(a)
#правый бинпоиск, который ищет правый границу
while right_1 - left_1 > 1:
middle = (right_1 + left_1) // 2
if a[middle] <= x:
left_1 = middle
else:
right_1 = middle
if left == left_1 and right == right_1:
print(0)
#возращение к следующей итерации с пропуском, что идет после него
continue
if right == left_1:
print(right + 1, right + 1)
else:
print(right + 1, left_1 + 1)
Приближенный двоичный поиск
Вот эта задачка с изюминкой! Тут надо так преобразовать поиск, чтобы выполнялось даже для чисел, которых нет в данном для поиска списке. Здесь мы также ищем середину в «граничном списке», затем элемент, который посередине сравниваем с числом, если он меньше него, мы записываем в левую границу (который индекс) индекс середины + 1(то есть не включаем прошлую середину в граничный список), в ином случае в правую границу записываем индекс середины. Все это делаем, пока левая граница меньше правой. После нахождения left и right рассматриваем случай, когда числа нет в списке и расстояние до того, что левее меньше или равно, чем то, что правее. Поэтому выводим a[left — 1], в ином случае a[left].
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
for x in b:
left = 0
right = n - 1
while left < right:
middle = (left + right) // 2
if a[middle] < x:
left = middle + 1
else:
right = middle
if left > 0 and a[left] != x and abs(a[left - 1] - x) <= abs(a[left] - x):
print(a[left - 1])
else:
print(a[left])
Квадратный корень и квадратный квадрат
Тадам! Задача на бинарный поиск по ответу. Для начала из библиотеки math подключим функцию sqrt, которая вычисляет квадратный корень, после определим для левой границы 0, а для правой 1e10, то есть 10 миллиардов, исходя из ограничений, которые указаны в условии. Далее как в типичном бинпоиске ищем середину, позже сравниваем. Но что тут интересного? Тут middle — это x в уравнении. Ввиду этого определяем значение уравнения и сверяем с реальным ответом (т.е. С). Ну и двигаем границы, до тех пор, пока разность границ не будет меньше или равна 10-ти миллиардным, это и есть точность измерения. Позже умножаем на миллион, округляем, переводим в int и вещественное деление на тот же миллион.
from math import sqrt
c = float(input())
left = 0
right = 1e10#1 c 10-тью нулями
while right - left > 10e-10:#10 нулей и 1
middle = (left + right) / 2
if middle * middle + sqrt(middle) >= c:
right = middle
else:
left = middle
#умножаем на 10e6, округляем, преобразуем в int, делим на 10e6
print(int(round(left*10e6))/10e6)
Очень Легкая Задача
Разбор на эту задачу уже есть, поэтому приложу только код.
n, x, y = map(int, input().split())
min1 = min(x, y)
if n == 1:
print(min1)
else:
left = 0
right = n * (x + y - min1 + 1)
while right - left > 1:
middle = (right + left) // 2
if n - 1 <= middle // x + middle // y:
right = middle
else:
left = middle
print(min1 + left + 1)
Для закрепления материала можно порешать задачи отсюда.
