Find the number of the first and last occurrence of an element in an array?

Question

C++ / C#

Left and Right Binary Search
Given two lists of numbers, the numbers in the first list are in non-decreasing 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.

Specifications Input

The first line of the input contains two numbers N and M (1≤N,M≤20000). The second line contains N integers sorted in non-decreasing order — the elements of the first list. The third line contains M non-negative integers — the elements of the second list. All numbers in the lists are 32-bit signed integers.

Output

The program should output M lines. For each number from the second list, print the number of its first and last occurrence in the first list. The numbering starts from one. If the number is not in the first list, output one number 0.

Examples
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

#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 1

What do you have there for a loop on k after calling binprisk? It is he who slows down making your program work in nm instead of m log n.
And yes - use lower_bound and upper_bound. This is exactly what you need.