A
A
asd1237asd2021-10-07 16:27:49
C++ / C#
asd1237asd, 2021-10-07 16:27:49

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;
}


Problem

Left and Right Binary Search
Given two lists of numbers, the numbers in the first list are sorted in non-descending order. For each number in the second list, determine the number of the first and last occurrence of that number in the first list. In this task, you can use the built-in functions.

in short, you need to speed up the program using lower_bound and upper_bound, somewhere to replace something. I will be very grateful!!!!!!!!!!!

Input
10 5
1 1 3 3 5 7 9 18 18 57
57 3 9 1 179
Output
10 10
3 4
7 7
1 2
0

Answer the question

In order to leave comments, you need to log in

2 answer(s)
W
Wataru, 2021-10-07
@wataru

In this task, you can use the built-in functions.

you need to speed up the program using lower_bound and upper_bound,

Well, look at these very lower_bound and upper_bound in the documentation. They just find the first and last inclusion of a given number, if it occurs in an ordered array. If the number is not there, then they will both point to the first greater number given.
Functions return iterators. To convert them to indices, you can use std::distance to get the distance to the beginning of the array. There are direct examples on the links above that all do this.

A
asd1237asd, 2021-10-08
@asd1237asd

Well can anyone help

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question