Debriefing tasks. Beanpoisk_1

Hello, dear Khabrovites. A series of articles contains a discussion of the tasks that are given in grade 8 at computer science lessons at the Chelyabinsk Physics and Mathematics Lyceum No. 31. A bit of history ... Our lyceum is one of the strongest educational institutions in Russia, which takes 5th place in the ranking on the competitiveness of graduates, losing to schools in Moscow and St. Petersburg. Pupils regularly win competitions at the national and international levels.
This article is devoid of theory; it contains only methods for solving problems. Details about bin search are described here.
So, let's move on to the tasks.These tasks involve the use of binary search, including bin search for answers. As we know, bin search is an algorithm for searching for objects by a given attribute in a set of objects. We apply for lists sorted in ascending / descending order. Only 4 tasks, 2 of which are aimed at applying the "algorithm without raisins . "

Left and right binary search

In this task, you must first consider the lengths of the first and second lines, then write each next line in a list. After we take each element of the second list and look for the right and left border for it. You may notice that if the number is not in the list, the total values ​​of the left border and the right border in the left and right bin search are equal.

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)

Approximate binary search

Here is this puzzle with a twist! Here it is necessary to transform the search so that it is performed even for numbers that are not in the list for the search. Here we also look for the middle in the “boundary list”, then the element that in the middle is compared with the number, if it is less than it, we write the mid index + 1 (that is, do not include the past middle in the boundary list) to the left border (which is the index), otherwise, in the right border we write the middle index. We do all this while the left border is smaller than the right. After finding left and right, we consider the case when the number is not in the list and the distance to the left is less than or equal to that to the right. Therefore, we deduce a [left - 1], otherwise 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])

Square root and square square

Tadam! The task of binary search by answer. To begin with, from the math library we connect the sqrt function, which calculates the square root, after which we define 0 for the left border, and 1e10 for the right border, that is, 10 billion, based on the restrictions specified in the condition. Next, as in a typical bin search, we are looking for the middle, later we compare. But what's interesting? Here middle is x in the equation. In view of this, we determine the value of the equation and compare it with the real answer (i.e., C). Well, we move the boundaries, until the difference in boundaries is less than or equal to 10 billion, this is the accuracy of the measurement. Later we multiply by a million, round off, translate into int and real division by the same million.

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)

Very Easy Challenge

There is already analysis for this task, so I will only attach the code.

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)

To consolidate the material, you can solve problems from here.