Бинарный поиск: поиск количества элементов

Question

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

Уже используется бинарный поиск.

Пример 1.

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

1 2 3 4 5 6 (массив)

0 6 2 1 11 (запрошенные числа)

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

0 1 1 1 0 (количество вхождений для каждого числа соответственно)

Пример 2.

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

1 1 1 1 1 (массив)

1 1 (запрошенные числа)

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

5 5 (количество вхождений для каждого числа соответственно)

Поскольку последовательность чисел отсортирована, была идея отсортировать и запрошенные числа по возрастанию, чтобы, найдя число или последовательность одинаковых чисел, исключить их из выборки, сдвинув левую границу для бинарного поиска на количество таких чисел вправо. То есть, не рассматривать числа, количество которых и так уже посчитано. Такое решение оптимально, но не сохраняет порядка запросов (количества вхождений выводятся в порядке возрастания запрошенных чисел, а не в порядке их ввода). В связи с этим вопрос: как реализовать одновременно быстрый - со сдвигом границы - алгоритм бинарного поиска и при этом вывести найденные количества в том порядке, в котором они были запрошены?

#include <iostream>
#include <vector>
using namespace std;

int findIndex(vector<int> arr, int n, int element)
{
    if (element > arr[n - 1])
    {
        return -1;
    }
    int left = 0, right = n - 1;
    
    while (right > left)
    {
        int middle = left + (right - left) / 2;
        if (element > arr[middle])
        {
            left = middle + 1;
        }
        else
        {
            right = middle;
        }
    }
    if (arr[left] == element)
    {
        return left;
    }
    else
        return -1;
}
int findQuanity(vector<int> arr, int n, int index)
{
    int element = arr[index];
    int quanity = 0;
    while (element == arr[index])
    {
        quanity++;
        if (index + 1 <= n - 1)
        {
            index++;
        }
        else break;
    }
    return quanity;
}
int main()
{
    int members;
    int element;
    cin >> members;
    
    vector<int> marks(members);

    for (int i = 0; i < members; i++)
    {
        cin >> marks[i];
    }
    int requests;
    cin >> requests;
    for (int i = 0; i < requests; i++)
    {
        cin >> element;
        int index = findIndex(marks, members, element);
        int quanity = 0;
        if (index > -1)
        {
            quanity = findQuanity(marks, members, index);
        }
        cout << quanity << endl;
    }

}

Answer 1

Раз в тэгах стоит c++, а массив является отсортированным, то сам Страуструп велел использовать стандартные алгоритмы lower_bound, upper_bound и distance. В коде это будет выглядеть как-то так:

  auto first = std::lower_bound(vec.begin(), vec.end(), val);
  auto last = std::upper_bound(vec.begin(), vec.end(), val);

  int count = std::distance(first, last);
  std::cout << count << std::endl;

Быстрее у вас вряд ли получится, разве что все это дело на Си написать

UPD обнаружил, что мой код не совсем рационален: поиск последнего элемента можно ускорить, так как мы знаем где находится первый

auto last = std::upper_bound(first, vec.end(), val);

БЛОГ НА HUSL

Бинарный поиск: поиск количества элементов

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