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

Ответы

olesya3010ozvprt 10.06.2021 17:56

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=' ')

Объяснение:

ПОКАЗАТЬ ОТВЕТЫ

Другие вопросы по теме Информатика

Versysbatl 03.07.2019 02:50

сана24 19.05.2021 14:58

veronikatulene 19.05.2021 14:59

cikitka2 19.05.2021 15:00

scattdipsizeoya3gc 02.02.2021 08:26

Какие вопросы решить электронное правительство РК?...

theodoorka 02.02.2021 08:26

lisa2051 02.02.2021 08:27

НастяandТима 23.09.2019 08:50

avatariyaflora 23.09.2019 09:00

Jillzay 23.09.2019 09:00