Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.63/8: Рейтинг темы: голосов - 8, средняя оценка - 4.63
pavel2210057
59 / 26 / 24
Регистрация: 28.09.2017
Сообщений: 374
Завершенные тесты: 2
1

Бинарный поиск без предварительной сортировки

16.03.2018, 14:25. Просмотров 1605. Ответов 45
Метки нет (Все метки)

Всем привет! Мне надо организовать двоичный поиск в массиве, но он не отсортирован по возрастанию или убыванию.
Вопрос: Как, если это возможно, найти элемент в таком массиве, методом бинарного дерева.
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.03.2018, 14:25
Ответы с готовыми решениями:

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

Бинарный поиск
Написал программу бинарного поиска элемента v. Не могу понять в чем ошибка, не считает количество...

Бинарный поиск
помоги мне плиз ответить на вопросы Бинарный поиск #include <iostream> using namespace std;...

Бинарный поиск
Что переделать в программе, чтобы она находила первый элемент больше или равный заданному? ...

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

45
TRam_
зомбяк
1290 / 975 / 285
Регистрация: 14.05.2017
Сообщений: 3,199
16.03.2018, 18:18 41
lArtl, а синхронизировать изменения у std::vector и std::set как будешь? std::shared_ptr вообще не понятно для чего указал.
0
lArtl
312 / 165 / 77
Регистрация: 09.10.2014
Сообщений: 787
Завершенные тесты: 3
16.03.2018, 20:01 42
Цитата Сообщение от TRam_ Посмотреть сообщение
lArtl, а синхронизировать изменения у std::vector и std::set как будешь? std::shared_ptr вообще не понятно для чего указал.
std::shared_ptr`ом и буду.
C++
1
2
3
4
5
6
7
std::vector<std::shared_ptr<T>> raw;
std::set<std::shared_ptr<T>> sorted;
...
auto item = std::make_shared<T>(...);
raw.push_back(item);
sorted.insert(std::move(item));
...
Добавлено через 9 минут
Смущает хранение std::shared_ptr в контейнере, но как тогда там в БД индексы реализованы?

Добавлено через 4 минуты
При условии, что удаление происходит редко (пробегаться по вектору придется линейно). Или мудрить со сохранением индекса в векторе...

Добавлено через 35 минут
А вообще можно почитать про БД, а именно про некластерные индексы, когда они нужны, а когда нет. В моем примере по сути std::vector - кластерный индекс, который отражает последовательность элементов, а std::set - некластерный, который придется перестраивать при изменении элемента( sorted.erase(item); sorted.insert(item).
0
TRam_
зомбяк
1290 / 975 / 285
Регистрация: 14.05.2017
Сообщений: 3,199
16.03.2018, 20:15 43
Цитата Сообщение от lArtl Посмотреть сообщение
std::shared_ptr`ом и буду
с std::shared_ptr'ом у тебя будет только гарантия того, что когда объект у тебя удалится только после того, как его сотрёшь/затрёшь новым и в векторе, и в set'е. А синхронизации удаления не будет.
0
lArtl
312 / 165 / 77
Регистрация: 09.10.2014
Сообщений: 787
Завершенные тесты: 3
16.03.2018, 20:20 44
Цитата Сообщение от woldemas Посмотреть сообщение
Можно что-нибудь придумать, наверное, какой нибудь связный список из блоков равной длины.
Ага, std::deque.
0
16.03.2018, 20:20
TRam_
зомбяк
1290 / 975 / 285
Регистрация: 14.05.2017
Сообщений: 3,199
16.03.2018, 20:21 45
Хотя... В общем в кое-в-чём ты прав. Так у нас действительно будет автоматически обновляемый указатель при перестроениях и set, и vector.
0
lArtl
312 / 165 / 77
Регистрация: 09.10.2014
Сообщений: 787
Завершенные тесты: 3
16.03.2018, 20:22 46
Цитата Сообщение от TRam_ Посмотреть сообщение
с std::shared_ptr'ом у тебя будет только гарантия того, что когда объект у тебя удалится только после того, как его сотрёшь/затрёшь новым и в векторе, и в set'е. А синхронизации удаления не будет.
Как и автоматического добавления в std::set при добавлении в std::vector... Все ручками.
0
16.03.2018, 20:22
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.03.2018, 20:22

Бинарный поиск
Реализовать алгоритм бинарного поиска количества нулевых элементов двумерного динамического...

Бинарный поиск
Каким образом выполнить бинарный поиск определнного значения в отсортированном массиве?

Бинарный поиск c++
1) последовательного поиска максимального элемента в одномерном динамическом массиве; 2) бинарного...


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

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

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