Найти номер первого и последнего вхождения элемента в масссив?

Question

[dmitrii2004]

Левый и правый двоичный поиск
Дано два списка чисел, числа в первом списке упорядочены по неубыванию. Для каждого числа из второго списка определите номер первого и последнего появления этого числа в первом списке. В данной задаче можно пользоваться встроенными функциями.

Входные данные

В первой строке входных данных записаны два числа N и M (1≤N,M≤20000). Во второй строке записаны N упорядоченных по неубыванию целых чисел — элементы первого списка. В третьей строке записаны M целых неотрицательных чисел — элементы второго списка. Все числа в списках — целые 32-битные знаковые.

Выходные данные

Программа должна вывести M строчек. Для каждого числа из второго списка нужно вывести номер его первого и последнего вхождения в первый список. Нумерация начинается с единицы. Если число не входит в первый список, нужно вывести одно число 0.

Примеры
Ввод
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

#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;
}
Программа выполнялась слишком долго

Comments

[Sergey]

Используйте lower_bound и upper_bound для определения позиции числа

Answer 1

[Wataru]

Что у вас там за цикл по k после вызова бинприска? Именно он и тормозит делая вашу программу работать за nm вместо m log n.

И да - используйте lower_bound и upper_bound. Это в точности то, что вам нужно.