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

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

Восстановить пароль Регистрация
 
Starfalll
0 / 0 / 0
Регистрация: 09.03.2013
Сообщений: 32
20.03.2013, 00:15     Двоичный (бинарный) поиск #1
Вот такой вот вопрос:
Есть например такой линейный массив
C++
1
1 1 1 1 2 3 4 5 6
Вводят какое-то число и нужно проверить сколько выступлений этого числа есть в массиве.

Я просто нахожу какое-то выступление числа и иду вправо и влево пока есть это число.
Но при очень больших массивах это заменяет очень много времени.
Как бинарным поиском находить первое выступление этого числа и последнее?

То есть вводят 1.
Как найти самую левую единицу и самую правую?
Чтобы потом просто отнять правую границу от левой и найти количество 1.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.03.2013, 00:15     Двоичный (бинарный) поиск
Посмотрите здесь:

Двоичный поиск C++
Двоичный поиск C++
Двоичный поиск C++
Двоичный(бинарный) поиск C++
двоичный поиск C++
двоичный поиск C++
Двоичный поиск C++
C++ Бинарный (двоичный) поиск по алфавиту в упорядоченном массиве структур

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
20.03.2013, 00:25     Двоичный (бинарный) поиск #2
как только в середину очередного интервала попала единица запускать два бинарных поиска. Один ищет левую границу последовательности единиц, другой - правую.
Yandex
Объявления
20.03.2013, 00:25     Двоичный (бинарный) поиск
Ответ Создать тему
Опции темы

Текущее время: 08:38. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru