0 / 0 / 0
Регистрация: 09.03.2013
Сообщений: 32
1

Двоичный(бинарный) поиск

17.03.2013, 15:27. Показов 2023. Ответов 1
Метки нет (Все метки)

Столкнулся с такой проблемой. использую бинарный поиск в упорядоченном массиве чисел для поиска количества повторений нужного мне числа
К примеру , есть массив чисел
C++
1
0 1 2 2 2 3
Ищу сколько 2 в нем есть.
Используя стандартный бинарный поиск мы находим 2 на 4 позиции и делим массив или на
C++
1
0 1 2
или на
C++
1
2 3
То есть и так и так в конце выдает что в массиве находится 2 двойки , что не есть правдой.
Все что я надумал , при нахождении нужного числа идем с помощью for в обе стороны пока находим нужное нам число.

Но ведь должно быть какое-то лучшее решение...или нет?
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
17.03.2013, 15:27
Ответы с готовыми решениями:

Двоичный (бинарный) поиск
Вот такой вот вопрос: Есть например такой линейный массив 1 1 1 1 2 3 4 5 6 Вводят какое-то...

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

Бинарный (двоичный) поиск по алфавиту в упорядоченном массиве структур
Приветствую товарищей-программистов! Есть массив структур StructWords massiv. struct...

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

1
~ Эврика! ~
1256 / 1005 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
17.03.2013, 16:40 2
Пишите бинарный поиск, манипулирующий границами интервалов. Граница — это нечто между элементами массива. Тогда у вас будет три интервала: слева, справа, и найденная двойка.

Или просто прибавьте единицу к тому, что получили, пройдя влево и вправо от найденного элемента. Всё равно он один.

Лучшее решение... Возможно, будет эффективнее использовать два подвида бинарного поиска: находящий самое левое вхождение и самое правое. Потом просто по разнице индексов определить количество. Но предпочтение этого метода простому линейному просмотру зависит от среднего количества повторений искомого элемента: при малом количестве повторений и большом массиве глянуть влево-вправо быстрее, чем делать ещё один поиск (а ещё поиск первого попавшегося элемента тоже чуть быстрее, чем поиск крайних).
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.03.2013, 16:40
Помогаю со студенческими работами здесь

Двоичный поиск
Формат входных данных В первой строке входных данных содержатся натуральные числа N и K...

двоичный поиск
Помогите, пожалуйста, модифицировать программу на рисунке, чтобы для выполнения двоичного поиска в...

Двоичный поиск
Добрый день. Помогите найти ошибку в двоичном поиске. Вот код: #include <iostream> #include...

Двоичный поиск
Помогите пожалуйста с двоичным поиском: нужно найти абитуриента с 287 баллами методом двоичного...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru