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

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

Комментарии (9)


  1. stavinsky
    11.03.2019 12:09
    +2

    Не сразу догадался что заголовки кликабельны.
    Хотелось бы больше теории и понимания зачем вы эту статью написали. Как-будто чего-то не хватает. Спасибо


    1. ratel_03 Автор
      11.03.2019 17:16

      Здравствуйте, спасибо за комментарий! Начало статьи изменил


  1. lamerok
    11.03.2019 12:36

    С корнем конечно работать будет, но странностей в этом коде очень много :)
    right = 1e10#1 c 10-тью нулями.
    Разрешающая способность числа с плавающей точкой примерно 7 знаков. Т.е. если вы прибавите, скажем к числу 100000001F + 1F, то получите тоже самое число.
    У вас выходит…
    middle * middle + sqrt(middle) — (10^10/2) * (10^10)/2 ~ 9 степень к ней вы прибавляете корень из 19 степени ~10 степень. Получаем к 19 степени вы прибавляете 10 степень… Разница 9 степеней. Т.е. сложение работать не будет, хотя условие if middle * middle + sqrt(middle) >= c конечно сработает верно. Но при этом, если программа изменится, и вы напишите c = double(input()). Вас, например, попросят поточнее решение найти — уже ничего работать не будет.
    Кроме того, хорошим тоном является брать в скобки все операции. Я конечно уверен, что вы знаете приоритеты всех операций и уверены что тут:
    if middle * middle + sqrt(middle) >= c все выполнится в такой вот последовательности:
    if (((middle * middle) + sqrt(middle)) >= c), а не в такой скажем
    if (middle * middle + (sqrt(middle) >= c)))
    Но лучше всегда ставить скобки, чтобы четко определить приоритет операций, не все программисты помнят приориты всех операций, а их скажем в С++ более 50.
    Еще одно замечания касается передачи параметра в функцию при сравнении
    if middle * middle + sqrt(middle) >= c
    тут в функцию sqrt передается параметр middle. Это хорошо, что sqrt его не меняет и вы это точно знаете. Но что если определении функции будет такое float sqrt(float&)? тогда вы передадите туда middle, оно там изменится и что в итоге будет проверяться в
    if sqrt(middle) + middle * middle >= c? что выполнится первым, вызов функции, изменение middle или умножение middle на middle, а потом вызов функции???
    Лучше взять корень, присвоить его временной переменной, а потом выполнить проверку в условии.

    Да и еще границы int от 2^31 до + 2^31. Если у вас print(int(round(left*10e6))/10e6) если left будет больше 2148, будет ерунда. Так как оно просто неверно преобразуется в int.
    В общем тут много загадок :) Скорее всего все надо считать в double, а не флоате. И вместо int использовать long long.


  1. IgorPie
    11.03.2019 12:52

    Жил был метод хорды и его усовершенствованная версия — метод половинного деления. И перекочевали они из вычислительной математики, в том числе и в виде «бинарного поиска».


  1. mayorovp
    11.03.2019 16:44

    Зачем вы каждый раз считываете числа n и m, а потом их не используете?

    Если это то что я думаю, то ваши решения могут не пройти любой из тестов просто из-за изменения в форматировании входного файла…


    1. ratel_03 Автор
      11.03.2019 17:23

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


    1. qw1
      11.03.2019 17:52

      решения могут не пройти любой из тестов просто из-за изменения в форматировании входного файла
      Почему, если в условии ясно написано
      Во второй строке задаются N чисел первого массива, отсортированного по неубыванию, а в третьей строке – K чисел второго массива.


      1. mayorovp
        11.03.2019 18:48

        Потому что на других площадках таких уточнений в условии может и не быть.


  1. 5nw
    11.03.2019 18:03

    Просто напомню что в Python для этого есть bisect, bisect_left и bisect_right
    В результате, получим такое решение первой задачи:


    import bisect
    
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    
    for v in b:
        left = bisect.bisect_left(a, v)
        if left >= n or a[left] != v:
            print(0)
        else:
            print(left + 1, bisect.bisect_right(a, v))

    В целях обучения это конечно не актуально, но на соревновании поможет сэкономить несколько минут