Python 3 Бинарный поиск Upper bound На вход подаются N целых чисел, а также набор из M запросов, каждый из которых — целое число. Ваша задача — для каждого запроса найти количество чисел из исходного набора, меньших либо равных заданному в запросе числу. Использовать встроенные функции бинарного поиска запрещено. Входные данные Первая строка содержит число N — количество элементов в массиве. 1≤N≤250000. Вторая строка содержит N целых чисел Ai через пробел. −109≤Ai≤109. Третья строка содержит число M — количество запросов. 1≤M≤250000. Четвёртая строка содержит M целых чисел Qi через пробел. −109≤Qi≤109. Выходные данные Выведите единственную строку с M целыми числами — количествами чисел исходного массива, меньших либо равных соответствующему запросу. Примеры Ввод Вывод 5 1 5 3 2 1 2 4 3 4 4
Ответы
Ответить на вопрос
Поделитесь своими знаниями, ответьте на вопрос:
Популярные вопросы в разделе
Составьте блок схему линейного алгоритма (9 класс)
Автор: Olesyamilenina8
Даны n чисел найти сумму только тех чисел которые не кратны 7 integer
Автор: Андрееевич787
написать программу на Паскале Обязательно с циклом procedure Error
Автор: filial2450
n = int(input())
ai = list(map(int, input().split()))
m = int(input())
qi = list(map(int, input().split()))
ai.sort()
for k in range(m):
i = 0
j = n - 1
counter = None
while i <= j:
mid = (i + j) // 2
if qi[k] == ai[mid]:
counter = mid
break
elif qi[k] < ai[mid]:
j = mid - 1
else:
i = mid + 1
counter = mid
print(counter + 1, end=' ')
Объяснение: