Analysis of tasks. Binpoisk_1

Hello, dear habrovchane. A series of articles contains an analysis of the tasks that are given in grade 8 in computer science lessons at Chelyabinsk Physics and Mathematics Lyceum No. 31. A bit of history ... Our high school is one of the strongest educational institutions in Russia, which ranks 5th in the ranking on the competitiveness of graduates, giving way to schools in Moscow and St. Petersburg. Pupils win regularly at national and international competitions.
This article is devoid of theory, it contains only ways to solve problems. Details about binpoisk are described here.
So, go to the tasks. These tasks involve the use of binary search, including bin search by answers. As we know, bin-search is an algorithm for searching objects by a given attribute in a set of objects. Apply to lists sorted in ascending / descending order. Only 4 tasks, 2 of which are aimed at applying the "algorithm without highlights" .

Left and right binary search

In this problem, you must first read the lengths of the first and second lines, then write each next line to the list. After we take each element of the second list and look for the right and left border for it. You can see 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 a problem with a twist! Here it is necessary to transform the search so that it is performed even for numbers that are not in the given search list. Here we also look for the middle in the “boundary list”, then the element that compares the middle with the number, if it is less than it, we write the midpoint + 1 in the left border (which is the index) otherwise, we write down the index of the middle in the right border. All this we do, while the left border is less than the right. After finding the 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 than the one 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! Task for binary search by answer. To begin with, from the math library, we include the sqrt function, which calculates the square root, after that 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. Further, as in a typical BinPoisk, we look for the middle, we compare it later. But what's so 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 (that is, C). Well, we move the boundaries, until the difference between the boundaries is less than or equal to 10 billionths, this is the measurement accuracy. Later we multiply by a million, we round up, we 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 Task

Analysis for this task is already there, so I will attach only 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 the problem from here.