Answer the question
In order to leave comments, you need to log in
Can you help me apply lower_bound and upper_bound in C++?
I myself deal only with JS, but I need to use the help of C ++, I don’t know the language at all, so I don’t know how to use functions
#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;
}
Answer the question
In order to leave comments, you need to log in
In this task, you can use the built-in functions.
you need to speed up the program using lower_bound and upper_bound,
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question