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

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

Новые блоги и статьи Все статьи Все блоги /
Оказывается, Unreal Engine позволяет качество на порядки выше, чем было в Lineedge Etyuhibosecyu 05.07.2026 Жаль, конечно, что я не узнал об этом, пока Lineedge существовала, а то бы Noname2331 написал, что волки превращаются в пиксельную кашу, а я бы его попросил скачать какую-нибудь бриллиантовую или Pro. . .	Doom для терминала без стрельбы и монстров. 3D Raycasting на ascii. dcc0 05.07.2026 Попросил нейронную сеть deepai. org написать рейкастинг 3D с библиотекой ncurses для Linux. Чтобы можно было ходить на стрелочки. Чтобы стены были отрисованы символами. Справилась. Первый вариант. . .	Установка статуса документа по условию Maks 05.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "НарядПутевка" разработанного в КА2. Задача: в табличной части "Материалы" документа при записи автоматически устанавливать статус. . .	Сезонность и суточность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .
В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .	интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .	Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .	Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .

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

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