Question

На питоне!!! СрочноРеализуйте алгоритм приближенного бинарного поиска.Входные данныеВ первой строке входных данных содержатся числа N и K. Во второй строке задаются N чисел первого массива, отсортированного по неубыванию, а в третьей строке – K чисел второго массива. Каждое число в обоих массивах по модулю не превосходит 2109.Выходные данныеДля каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному. Если таких несколько, выведите меньшее из них.Примерывходные данные5 51 3 5 7 9 2 4 8 1 6 выходные данные13715

Answer 1

Просто прогоняем бинарный поиск дважды, сначала ищем ближайшее число, не большее нужного, потом не меньшее. Для того, чтобы такие числа были, можно дописать в массив очень большое число и очень маленькое. Затем выбираем из этих двух найденных чисел то, что будет ближе.

Пример реализации:

def bin_search(arr, target, kind="<="):

   assert kind in ["<=", ">="]

   if kind == "<=":

       comp = lambda a, b: a <= b

   else:

       comp = lambda a, b: a < b

   l = 0

   r = len(a) - 1

   while l < r - 1:

       m = (l + r) // 2

       if comp(a[m], target):

           l = m

       else:

           r = m

   if kind == "<=":

       return arr[l]

   else:

       return arr[r]

def nearest(arr, target):

   nearest_le = bin_search(arr, target, "<=")

   nearest_ge = bin_search(arr, target, ">=")

   if nearest_ge - target < target - nearest_le:

       return nearest_ge

   else:

       return nearest_le

_ = input()

a = [int(x) for x in input().split()]

a = [float("-Infinity")] + a + [float("+Infinity")]

for target in map(int, input().split()):

   print(nearest(a, target))

Answer 2

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

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

Далее, для каждого числа из второго массива, необходимо найти наиболее близкое число в первом массиве. Для этого можно использовать приближенный бинарный поиск.

Алгоритм приближенного бинарного поиска работает следующим образом: 1. Инициализируем переменные left и right, которые будут представлять левую и правую границы для бинарного поиска. Изначально left = 0, right = N-1. 2. Пока left <= right: - Вычисляем индекс середины массива: mid = (left + right) // 2. - Если число в массиве с индексом mid равно искомому числу, то это и есть наиболее близкое число. Возвращаем его. - Если число в массиве с индексом mid больше искомого числа, то обновляем right = mid - 1. - Если число в массиве с индексом mid меньше искомого числа, то обновляем left = mid + 1. 3. Если после цикла left > right, то наиболее близкое число будет находиться в массиве с индексом right.

Применяя данный алгоритм для каждого числа из второго массива, можно найти наиболее близкое число в первом массиве и вывести его.

Пример реализации на языке Python:

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

while left <= right:
        mid = (left + right) // 2

if arr[mid] == target:
            return arr[mid]
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

return arr[right]

# Считываем входные данные
N, K = map(int, input().split())
arr1 = list(map(int, input().split()))
arr2 = list(map(int, input().split()))

# Для каждого числа из второго массива находим наиболее близкое число в первом массиве
for num in arr2:
    closest_num = binary_search(arr1, num)
    print(closest_num)

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