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

@ТимурКаримов · Регистрация: 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), кто мешает оттуда содрать и разобраться как оно работает?

Новые блоги и статьи Все статьи Все блоги /
Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .	Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .
Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .	Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .	Создание формы заимствованного документа Maks 03.08.2026 Задача: Необходимо создать собственную форму заимствованного документа. На форме должен быть реквизит "Покупатель", а также табличная часть со следующими реквизитами: - Расчетный счет покупателя. . .	Задача предоставления скидок покупателям Maks 03.08.2026 Задача: В документе "Продажи" необходимо реализовать функционал предоставления скидок покупателям. Скидка должна автоматически рассчитываться и подставляться в соответствующее поле при выборе. . .

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

	Бинарный поиск для нахождения количества повторяющихся элементов 18.03.2016, 12:34. Показов 23507. Ответов 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

Опции темы