Сам занимаюсь только с JS, но нужно воспользоваться помощью С++, язык вообще не знаком, соответственно не знаю как использовать функции
#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
#include <algorithm>
void fillVector(std::vector<int>& numbers)
{
std::vector<int>::iterator i = numbers.begin();
for (; i != numbers.end(); ++i) {
*i = 1 + rand() % 10;
}
}
void printVector(const std::vector<int>& numbers)
{
for (const auto& x : numbers) {
std::cout << x << " ";
}
std::cout << std::endl;
}
int binSearchLeft(const std::vector<int>& numbers, int value)
{
int left = -1;
int right = numbers.size();
while (right - left > 1) {
int middle = (left + right) / 2;
if (numbers[middle] < value) {
left = middle;
}
else {
right = middle;
}
}
return left;
}
int binSearchRight(const std::vector<int>& numbers, int value)
{
int left = -1;
int right = numbers.size();
while (right - left > 1) {
int middle = (left + right) / 2;
if (numbers[middle] <= value) {
left = middle;
}
else {
right = middle;
}
}
return right;
}
int main()
{
srand(time(nullptr));
int n, m;
std::cin >> n >> m;
std::vector<int> nNumbers(n), mNumbers(m);
fillVector(nNumbers);
std::sort(nNumbers.begin(), nNumbers.end());
fillVector(mNumbers);
printVector(nNumbers);
printVector(mNumbers);
for (std::vector<int>::iterator i = mNumbers.begin(); i != mNumbers.end(); ++i) {
int left = binSearchLeft(nNumbers, *i);
int right = binSearchRight(nNumbers, *i);
if (right - left < 2) {
std::cout << 0 << std::endl;
continue;
}
else {
for (size_t k = left + 2; k <= right; ++k) {
if (right - left == 2) {
std::cout << k << " " << k << " ";
}
else {
std::cout << k << " ";
}
}
std::cout << std::endl;
}
}
return 0;
}
Задача
Левый и правый двоичный поиск
Дано два списка чисел, числа в первом списке упорядочены по не убыванию. Для каждого числа из второго списка определите номер первого и последнего появления этого числа в первом списке. В данной задаче можно пользоваться встроенными функциями.
короче, надо ускорить программу с помощью lower_bound и upper_bound, где-то что-то заменить. Буду очень благодарен!!!!!!!!!!!
Ввод
10 5
1 1 3 3 5 7 9 18 18 57
57 3 9 1 179
Вывод
10 10
3 4
7 7
1 2
0
