Разбор задач. Бинпоиск_1

Здравствуйте, уважаемые хабровчане. Серия статей содержит разбор задач, которые дают в 8 классе на уроках информатики в Челябинском физико-математическом лицее №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)

Для закрепления материала можно порешать задачи отсюда.