汇报任务。 Beanpoisk_1

您好，亲爱的哈布罗维特。 一系列文章讨论了在车里雅宾斯克物理和数学学院第31号计算机科学课上八年级时给出的任务。 悠久的历史...我们的中学是俄罗斯最强大的教育机构之一，在毕业生竞争力排名中名列第五，在莫斯科和圣彼得堡败北。 学生定期赢得国家和国际比赛。
本文缺乏理论；仅包含解决问题的方法。 此处介绍有关bin搜索的详细信息。
因此，让我们继续执行任务。 这些任务涉及二进制搜索的使用，包括bin搜索答案。 众所周知，bin搜索是一种通过一组对象中给定属性搜索对象的算法。 我们申请按升序/降序排列的列表。 只有4项任务，其中2项旨在应用“没有葡萄干的算法”。

左右二进制搜索

在此任务中，您必须首先考虑第一行和第二行的长度，然后将每个下一行写入列表中。 之后，我们获取第二个列表的每个元素，并为其寻找左右边界。 您可能会注意到，如果该数字不在列表中，则左右bin搜索中的左边界和右边界的总值是相等的。

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-1]，否则得出[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]) 

平方根和平方平方

塔达姆！ 通过答案进行二进制搜索的任务。 首先，从数学库中连接sqrt函数，该函数计算平方根，然后根据条件中指定的限制为左边界定义0，为右边界定义1e10，即100亿。 接下来，就像在典型的bin搜索中一样，我们正在寻找中间位置，稍后我们进行比较。 但是有趣的是什么？ 在方程式中，中间是x。 有鉴于此，我们确定方程的值，并将其与实际答案（即C）进行比较。 好吧，我们移动边界，直到边界之差小于或等于100亿，这就是测量的准确性。 后来我们乘以一百万，四舍五入，将整数和实数除以同一百万。

 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) 

为了巩固材料，您可以从这里解决问题。