Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.60/25: Рейтинг темы: голосов - 25, средняя оценка - 4.60
0 / 0 / 0
Регистрация: 03.06.2022
Сообщений: 8

Задача на бинарный поиск

18.07.2022, 21:38. Показов 5622. Ответов 6
Метки c++ (Все метки)

Студворк — интернет-сервис помощи студентам
Вот такая задача:

Дан массив из N целых чисел. Все числа от −10^9 до 10^9. Нужно уметь отвечать на запросы вида “Cколько чисел имеют значения от L до R?”.

Формат ввода

Число N (1≤N≤105). Далее N целых чисел.Затем число запросов K (1≤K≤10^5). Далее K пар чисел L,R ( −10^9≤L≤R≤10^9) собственно запросы.

Формат вывода

Выведите K чисел — ответы на запросы.

Мой код вот такой:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main()
{
    int n,k, ans = 0;
    long int l, r, m, x, l1, r1;
    cin >> n;
    vector<long int> a;
    a.reserve(n);
    for (int i = 0; i < n; ++i) {
        cin >> x;
        a.push_back(x);
    }
    
    sort(a.begin(), a.end());
 
   cin >> k;
   
   
}
Ответ находится через 2 бинарных поиска. Помогите пожалуйста их написать!
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
18.07.2022, 21:38
Ответы с готовыми решениями:

Задача про провода: бинарный поиск
Дано N отрезков провода длиной L1, L2, ..., LN сантиметров. Требуется с помощью разрезания получить из них K равных отрезков как можно...

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

Бинарный поиск
Каким образом выполнить бинарный поиск определнного значения в отсортированном массиве?

6
Объявлятель переменных
 Аватар для SpBerkut
1225 / 411 / 321
Регистрация: 24.09.2011
Сообщений: 1,279
19.07.2022, 06:45
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <vector>
#include <algorithm>
 
int main()
{
    unsigned n, k;
 
    std::cin >> n;
    std::vector<long int> a ( n );
    
    for (auto& x : a) {
        std::cin >> x;
    }
 
    std::sort(a.begin(), a.end());
 
    std::cin >> k;
    while (k--) {
        long int l, r;
        std::cin >> l >> r;
        std::cout << std::distance( a.begin(), std::upper_bound( a.begin(), a.end(), r )) -
                     std::distance( a.begin(), std::lower_bound( a.begin(), a.end(), l )) << std::endl;
    }
}
1
4 / 4 / 0
Регистрация: 24.07.2022
Сообщений: 6
24.07.2022, 02:59
SpBerkut, разве так не проще?
C++
1
std::upper_bound(a.begin(), a.end(), r) - std::lower_bound(a.begin(), a.end(), l)
0
4 / 4 / 0
Регистрация: 24.07.2022
Сообщений: 6
24.07.2022, 03:00
SpBerkut, разве так не проще?
C++
1
std::upper_bound(a.begin(), a.end(), r) - std::lower_bound(a.begin(), a.end(), l)
0
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38180 / 21115 / 4307
Регистрация: 12.02.2012
Сообщений: 34,722
Записей в блоге: 14
24.07.2022, 05:04
Цитата Сообщение от Harion Посмотреть сообщение
Дан массив из N целых чисел. Все числа от −10^9 до 10^9.
- и это все? Числа могут быть перемешаны? Тогда бинарный поиск неприменим.
0
 Аватар для Kuzia domovenok
4268 / 3327 / 926
Регистрация: 25.03.2012
Сообщений: 12,536
Записей в блоге: 1
24.07.2022, 11:07
Catstail, именно поэтому он вызывает sort, а не подразумевает, что массив вводится уже сортированным

Добавлено через 1 минуту
сохранять порядок чисел не важно, важно толко количество совпадений с запросами
0
 Аватар для lemegeton
4903 / 2696 / 921
Регистрация: 29.11.2010
Сообщений: 5,783
24.07.2022, 13:04
Можно чууть-чуть ускорить код уважаемого SpBerkut, если искать r после l.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <vector>
#include <algorithm>
 
int main()
{
    unsigned n, k;
 
    std::cin >> n;
    std::vector<long int> a ( n );
 
    for (auto& x : a) {
        std::cin >> x;
    }
 
    std::sort(a.begin(), a.end());
 
    std::cin >> k;
    while (k--) {
        long int l, r;
        std::cin >> l >> r;
        auto lower = std::lower_bound(a.begin(), a.end(), l);
        auto upper = std::upper_bound(lower, a.end(), r); // типа не с первого элемента, а с левого
        std::cout << std::distance(lower, upper) << std::endl;
    }
}
Ничтожный прирост с учётом логарифмической сложности алгоритма.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
24.07.2022, 13:04
Помогаю со студенческими работами здесь

Бинарный поиск
Как пофиксить? Поиск работает через раз. Вывод отсутствие элемента как правило во второй части или середине, хотя число есть. #include...

Бинарный поиск
Реализация на С++: int Search_Binary (int arr, int left, int right, int key) { int midd = 0; while (1) { midd = (left +...

Бинарный поиск
Не находит нужный элемент. Сообщение что элемент отсутствует. #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include...

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

Бинарный поиск
Написал программу бинарного поиска элемента v. Не могу понять в чем ошибка, не считает количество элементов массива удовлетворяющий...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Новые блоги и статьи
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий
8Observer8 02.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru