Левый и правый двоичный поиск c++

Question

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

Собственно в чем вопрос. Код сам есть, но он не проходит несколько тестов. Прошу помощи

#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
#include <algorithm>



long binSearchLeft(const std::vector<int>& numbers, int value)
{
long left = -1;
long right = numbers.size();

while (right - left > 1) {
    long middle = (left + right) / 2;
    if (numbers[middle] < value) {
        left = middle;
    } else {
        right = middle;
    }
}
return left;
}

long binSearchRight(const std::vector<int>& numbers, int value)
{
long left = -1;
long right = numbers.size();

while (right - left > 1) {
    long middle = (left + right) / 2;
    if (numbers[middle] <= value) {
        left = middle;
    } else {
        right = middle;
    }
}
return right;
}


int main()
{

int n, m;
std::cin >> n >> m;

std::vector<int> nNumbers(n), mNumbers(m);

for(auto& elem : nNumbers)
   std::cin >> elem;
std::sort(nNumbers.begin(), nNumbers.end());

for(auto& elem : mNumbers)
    std::cin >> elem;


for (std::vector<int>::iterator i = mNumbers.begin(); i != mNumbers.end(); ++i) {
    long left = binSearchLeft(nNumbers, *i);
    long 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

Как я понял, у нас есть два списка один отсортирован другой нет, нам надо найти все границы встречи элементов второго списка в первом. Так же я понял нам надо добиться O(mlogn, где m размер второго списка. Перове, что мы сделаем, отсортируем второй список, это позволит нам не пересчитывать один и тот же элемент по несколько раз. Дальше, проходимся и ищем элементы сначала меньшие данного, потом больше. Для этого отлично подходит двоичный поиск. Мы будем использовать не обычное реализацию с медианами подотрезка, мы будем использовать двоичный поиск с прыжками, сначала с одной стороны, потом с другой. Длина каждого прыжка n/k, где k=2 => k/=2, пока мы не найдем нужный элемент, это позволяет добиться логарифмического множителя. Вот сама реализация двочиного поиска, я думаю не составит труда запустить его с обратной стороны

int binary_search(vector <int> data, int f_x){
    int k = 0;
    for (int b = data.size()/2; b>=1; b/=2){
        while(k+b<data.size() && data[k+b]<=f_x) k+=b;
    }
    return k;
    
}

более простой метод, без двоичного поиска, пройтись за O(n) по первому списку и записать в map <int, pair <int, int>> элемент его начальный индекс и конечный, и тогда для каждого запроса из второго списка мы будем за find в set [log(n)] находить его границы в первом. Вот как это можно реализовать:

vector <int>  data = {1,1,1,2,2,2,2,2,2,3,3,3,3,3,4};
    map <int, pair <int, int>> pool;
    bool nnext = true;
    for(int i = 0;i < data.size(); i++){
        if (nnext){
            pool[data[i]].first = i;   
            nnext = false;
        }
        if (data[i]!=data[i+1] || i+1>=data.size()){
            nnext = true;
            pool[data[i]].second = i;
        }
        
    }

БЛОГ НА HUSL

Левый и правый двоичный поиск c++

Ответы (1 шт):