Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Starfalll
0 / 0 / 0
Регистрация: 09.03.2013
Сообщений: 32
#1

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

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

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

Но ведь должно быть какое-то лучшее решение...или нет?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.03.2013, 15:27
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Двоичный(бинарный) поиск (C++):

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

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

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

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

Двоичный поиск - C++
Требуется найти в массиве элементы которые повторяются и элементы которые присутствуют единожды. #include <stdafx.h> #define N 10 ...

Двоичный поиск - C++
Добрый день. Помогите найти ошибку в двоичном поиске. Вот код: #include <iostream> #include <conio.h> using namespace std; int...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
OhMyGodSoLong
~ Эврика! ~
1243 / 992 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
17.03.2013, 16:40 #2
Пишите бинарный поиск, манипулирующий границами интервалов. Граница — это нечто между элементами массива. Тогда у вас будет три интервала: слева, справа, и найденная двойка.

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

Лучшее решение... Возможно, будет эффективнее использовать два подвида бинарного поиска: находящий самое левое вхождение и самое правое. Потом просто по разнице индексов определить количество. Но предпочтение этого метода простому линейному просмотру зависит от среднего количества повторений искомого элемента: при малом количестве повторений и большом массиве глянуть влево-вправо быстрее, чем делать ещё один поиск (а ещё поиск первого попавшегося элемента тоже чуть быстрее, чем поиск крайних).
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.03.2013, 16:40
Привет! Вот еще темы с ответами:

Двоичный поиск - C++
Помогите пожалуйста с двоичным поиском: нужно найти абитуриента с 287 баллами методом двоичного поиска.. #include <iostream.h> ...

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

Двоичный поиск - C++
Нашел на форуме двоичный поиск, не подскажите как нужно изменить код, что бы программа выводила еще и индекс, в котором находится введенное...

двоичный поиск - C++
Подскажите, пожалуйста, в вопросе: Какое дополнительное требование к массиву может быть применено при двоичном поиске, что бы определить...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru