Question

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

Answer 1

Ответ:

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

Объяснение:

Answer 2

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

1. Сначала отсортируйте массив Ai.
2. Для каждого запроса Qi, найдите количество элементов массива, которые меньше или равны Qi с использованием бинарного поиска.

Вот Python-код, который выполняет эту задачу:

pythonCopy code
# Функция для подсчета количества элементов в массиве меньше или равных заданному числу
def count_elements_less_than_or_equal(arr, x):
    left, right = 0, len(arr) - 1
    count = 0

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] <= x:
            count = mid + 1
            left = mid + 1
        else:
            right = mid - 1

    return count

# Чтение входных данных
n = int(input())
arr = list(map(int, input().split()))
m = int(input())
queries = list(map(int, input().split()))

# Сортировка массива
arr.sort()

# Обработка запросов и вывод ответов
results = []
for q in queries:
    count = count_elements_less_than_or_equal(arr, q)
    results.append(count)

# Вывод ответов
print(" ".join(map(str, results)))

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