Бинарный поиск для нахождения количества повторяющихся элементов

@ТимурКаримов · Регистрация: 15.12.2015

Студворк — интернет-сервис помощи студентам

Здравствуйте.
Стоит следующая несложная задача:
Дан массив (отсортированный).
Например
1 1 1 4 5 6 6 6 6 6 6 6
При вводе числа 6 на выходе должны получить
7.
Иными словами, показать количество повторений искомого элемента.
Была идея сделать сперва бинарный поиск элемента с левой стороны, потом с правой, а после отнять координаты и +1, и имеем количество элементов.
Но, алгоритм должен работать O(logn). Если я буду использовать сразу 2 почти аналогичные функций бинарного поиска, сохранится ли эта сложность, или возрастёт?
Если есть какие-то идеи, как сделать быстрее, буду признателен!

Спасибо

@programmist- · 21.08.2020, 11:42

Повторяю, решение полностью рабочее, в тестирующей системе оно набирает полный балл. Я не использую лишних циклов, лишь тот же, где и производится ввод всего массива. Здесь потерь памяти и времени нет. Задача была на бинарный поиск, функция бин поиска вернёт индекс на элемент в массива, либо -1 если его нет. Как вы говорите, я не сортирую массив, он уже отсортирован при вводе

Добавлено через 5 минут
Более того, изначально программа писалась для ответов на запросы по нескольким числам. Было дано m чисел и нужно было ответить на вопрос для каждого из них. Программа также успешно работала, не занимая многоп амяти. Тестирующая система с лёгкостью приняла

@Avazart · 21.08.2020, 11:43

TheCalligrapher, И тем не менее в приводимых реализация алгоритмов все же - и + я не могу припомнить.
Более того через ф-ции как я помню идут проверки в дебаге на выход за пределы.

@TheCalligrapher · 21.08.2020, 23:38

Сообщение от programmist-

Повторяю, решение полностью рабочее

Нет, решение не "рабочее". Неопределенное поведение - дальше можно не смотреть.

Сообщение от programmist-

Я не использую лишних циклов, лишь тот же, где и производится ввод всего массива.

То есть задача решается за два цикла - как и во всех остальных решениях, но при этом делает лишнюю работу и тратит лишнюю память.

Сообщение от programmist-

Здесь потерь памяти и времени нет.

Потери памяти и времени - ясно указаны в моем предыдущем сообщении.

Сообщение от programmist-

Более того, изначально программа писалась для ответов на запросы по нескольким числам.

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

Сообщение от programmist-

в тестирующей системе оно набирает полный балл.

Сообщение от programmist-

Тестирующая система с лёгкостью приняла

Это ничего не доказывает.

@alexu_007 · 22.08.2020, 07:54

Сообщение от TheCalligrapher

Для std::lower_bound гарантируется логарифмическое количество сравнений, то есть как ни верти, поиск должен быть построен на некоей "подразбивающей" стратегии (читай: да, это бинарный поиск).

Я так понимаю, учебная задача подразумевает реализацию бинарного поиска "вручную", а не поиск и использование подходящего оператора?

@AndryS1 · 22.08.2020, 17:15

Сообщение от alexu_007

учебная задача подразумевает реализацию бинарного поиска "вручную"

а где сказано что это учебная задача?

@Avazart · 22.08.2020, 17:39

Сообщение от alexu_007

Я так понимаю, учебная задача подразумевает реализацию бинарного поиска "вручную", а не поиск и использование подходящего оператора?

Какого еще оператора ?

@alexu_007 · 23.08.2020, 04:45

C
1
std::lower_bound

@Avazart · 23.08.2020, 13:05

Это оператор?
Это шаблон функции, так же известный как "алгоритм ст.библиотеки".

@TheCalligrapher · 23.08.2020, 21:18

Сообщение от alexu_007

Я так понимаю, учебная задача подразумевает реализацию бинарного поиска "вручную", а не поиск и использование подходящего оператора?

Не могу сказать. Бывают учебные задачи на умение реализовать бинарный поиск вручную. Бывают учебные задачи на умение работать со стандартной библиотекой, т.е. не изобретать велосипед. И то, и другое по-своему ценно. О чем идет речь в данном случае нужно спрашивать у ТС.

@Avazart · 23.08.2020, 21:48

Сообщение от TheCalligrapher

Бывают учебные задачи на умение реализовать бинарный поиск вручную. Бывают учебные задачи на умение работать со стандартной библиотекой, т.е. не изобретать велосипед. И то, и другое по-своему ценно.

Или нет.
Может лучше комбинировать, почему не учить писать свою стандартную библиотеку ?

А если без шуток то тут std::lower_bound есть примеры возможной реализации алгоритма(Possible implementation), кто мешает оттуда содрать и разобраться как оно работает?

Новые блоги и статьи Все статьи Все блоги /
Транслитерация текста с кириллицы на латиницу (вариант №2) Maks 13.11.2026 Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .	Часы с термометром и праздничным календарем yariko 12.11.2026 Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .	Транслитерация текста с кириллицы на латиницу (вариант №1) Maks 11.11.2026 Решил облегчить жизнь себе и коллегам админам при создании электронных почтовых ящиков для пользователей, в результате написал обработку "Транслитерация текста" с кириллицы на латиницу, а в ней. . .	Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .
Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят zorxor 08.11.2026 Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .	Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .	Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .	Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .

@ТимурКаримов 0 / 0 / 0 Регистрация: 15.12.2015 Сообщений: 16

	Бинарный поиск для нахождения количества повторяющихся элементов 18.03.2016, 12:34. Показов 23679. Ответов 29 Метки нет (Все метки) Здравствуйте. Стоит следующая несложная задача: Дан массив (отсортированный). Например 1 1 1 4 5 6 6 6 6 6 6 6 При вводе числа 6 на выходе должны получить 7. Иными словами, показать количество повторений искомого элемента. Была идея сделать сперва бинарный поиск элемента с левой стороны, потом с правой, а после отнять координаты и +1, и имеем количество элементов. Но, алгоритм должен работать O(logn). Если я буду использовать сразу 2 почти аналогичные функций бинарного поиска, сохранится ли эта сложность, или возрастёт? Если есть какие-то идеи, как сделать быстрее, буду признателен! Спасибо 0

@programmist- 0 / 0 / 0 Регистрация: 11.08.2020 Сообщений: 23
	21.08.2020, 11:42
	Повторяю, решение полностью рабочее, в тестирующей системе оно набирает полный балл. Я не использую лишних циклов, лишь тот же, где и производится ввод всего массива. Здесь потерь памяти и времени нет. Задача была на бинарный поиск, функция бин поиска вернёт индекс на элемент в массива, либо -1 если его нет. Как вы говорите, я не сортирую массив, он уже отсортирован при вводе Добавлено через 5 минут Более того, изначально программа писалась для ответов на запросы по нескольким числам. Было дано m чисел и нужно было ответить на вопрос для каждого из них. Программа также успешно работала, не занимая многоп амяти. Тестирующая система с лёгкостью приняла 0

@Avazart 8489 / 6156 / 615 Регистрация: 10.12.2010 Сообщений: 28,683 Записей в блоге: 30
	21.08.2020, 11:43
	TheCalligrapher, И тем не менее в приводимых реализация алгоритмов все же - и + я не могу припомнить. Более того через ф-ции как я помню идут проверки в дебаге на выход за пределы. 0

@Avazart 8489 / 6156 / 615 Регистрация: 10.12.2010 Сообщений: 28,683 Записей в блоге: 30
	23.08.2020, 13:05
	Это оператор? Это шаблон функции, так же известный как "алгоритм ст.библиотеки". 0