Есть задача:
На вход подаются N целых чисел, а также набор из M запросов, каждый из которых — целое число. Ваша задача — для каждого запроса найти количество чисел из исходного набора, меньших заданного в запросе числа. Использовать встроенные функции бинарного поиска запрещено.
Пример:
Ввод:
5
1 5 3 2 1
2
4 3
Вывод:
4 3
Я написал такой код на Python:
def sort(a : list, x):
L = -1
R = len(a)
while R - L > 1:
M = (R + L) // 2
if a[M] < x:
L = M
else:
R = M
return R
n = int(input())
a = sorted(list(map(int, input().split())))
m = int(input())
b = list(map(int, input().split()))
for q in b:
r = sort(a, q)
print(r)
Он работает отлично.
Вот тот же код на C++:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int count(vector<int> a, int x)
{
int l = -1;
int r = a.size();
while (r - l > 1)
{
int m = (r + l) / 2;
(a[m] < x ? l : r) = m;
}
return r;
}
int main()
{
int n, m; cin >> n;
vector<int> a (n);
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a.begin(), a.end());
cin >> m;
vector<int> b (m);
for (int i = 0; i < m; i++)
cin >> b[i];
for (int q: b)
cout << count(a, q) << " ";
}
Но он работает слишком медленно.
Прошу, помогите, как можно ускорить работу данного кода на С++?
count(vector<int> a
- каждый вызов копирует вектор целиком. Сложность создания копии - линейная. На её фоне двоичный (за логарифм) поиск теряется.int count(vector<int> &a, int x)