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

@pavel2210057 · Регистрация: 28.09.2017

Студворк — интернет-сервис помощи студентам

Всем привет! Мне надо организовать двоичный поиск в массиве, но он не отсортирован по возрастанию или убыванию.
Вопрос: Как, если это возможно, найти элемент в таком массиве, методом бинарного дерева.

@TRam_ · 16.03.2018, 18:18

lArtl, а синхронизировать изменения у std::vector и std::set как будешь? std::shared_ptr вообще не понятно для чего указал.

@lArtl · 16.03.2018, 20:01

Сообщение от 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)

.

@TRam_ · 16.03.2018, 20:15

Сообщение от lArtl

std::shared_ptr`ом и буду

с std::shared_ptr'ом у тебя будет только гарантия того, что когда объект у тебя удалится только после того, как его сотрёшь/затрёшь новым и в векторе, и в set'е. А синхронизации удаления не будет.

@lArtl · 16.03.2018, 20:20

Сообщение от woldemas

Можно что-нибудь придумать, наверное, какой нибудь связный список из блоков равной длины.

Ага, std::deque.

@TRam_ · 16.03.2018, 20:21

Хотя... В общем в кое-в-чём ты прав. Так у нас действительно будет автоматически обновляемый указатель при перестроениях и set, и vector.

@lArtl · 16.03.2018, 20:22

Сообщение от TRam_

с std::shared_ptr'ом у тебя будет только гарантия того, что когда объект у тебя удалится только после того, как его сотрёшь/затрёшь новым и в векторе, и в set'е. А синхронизации удаления не будет.

Как и автоматического добавления в std::set при добавлении в std::vector... Все ручками.

Новые блоги и статьи Все статьи Все блоги /
Krabik для WoW 3.3.5a, многоязычный AmbA 02.07.2026 Допилил бота, думаю что окончательно. Изменения: - добавлена многоязычность - добавлено снятие скриншотов - добавлено поддержание бафов хождения по воде (для жреца, дк и шамана) - и так, по. . .	Алиса нашла кучу ошибок компиляции и запуска в проекте, который без проблем компилировался и запускался))) anaschu 30.06.2026 Я пока посмеюся, но завтра проверю. А вообще интерсно. Дал алисе файл, в котором точно нет ошибок компиляции и запуска, и попросил их найти. Нашла кучу))) Критические ошибки, мешающие компиляции и. . .	сукцессия 16. Общий обзор, в основном что бы другие ии поняли anaschu 29.06.2026 # Передаточный документ: модель микоризной сукцессии (для нового чата) Этот документ предназначен для того, чтобы новый чат Claude мог продолжить работу без необходимости заново разбираться в. . .	сукцессия 15 неявная схема anaschu 29.06.2026 Алиса Калибровка параметров симбиотической модели: технический обзор Содержание: Введение Постановка проблемы Технические аспекты реализации Процесс внедрения изменений
сукцессия 14. Обновленная схема модели anaschu 28.06.2026 ГЛОБАЛЬНАЯ ОПИСАТЕЛЬНАЯ СПЕЦИФИКАЦИЯ ЭКОСИСТЕМНОЙ МОДЕЛИ «SOIL CHEMISTRY & MYCORRHIZA 2. 0» https:/ / ibb. co/ NnkGpfMd Представленная интегрированная схема описывает непрерывную нелинейную. . .	сукцессия 13. Питон модель трехзонного мицелия, пока что в основном арбускулярного anaschu 28.06.2026 ## Разработка агентной модели микоризной сукцессии: от выявления артефактов к созданию комплексной системы ### Аннотация Представлено исследование по разработке агентной модели микоризной. . .	сукцессия 12. краткий список проверок модели перед запуском. anaschu 27.06.2026 Скрытые отказы в моделях систем динамики (SD-models) экологических систем: два случая из практики Контекст Разбирался прототип модели систем динамики (SD-модели) микоризной сукцессии: пять. . .	Сукцессия 11. Проверка орудий перед войной: разработка через тестирование anaschu 27.06.2026 Как не дать модели соврать самой себе: проверки для симуляции микоризной сукцессии Введение Когда вы строите математическую модель живой системы — грибов, растений, почвы — главная опасность. . .

@pavel2210057 61 / 28 / 24 Регистрация: 28.09.2017 Сообщений: 399

	Бинарный поиск без предварительной сортировки 16.03.2018, 14:25. Показов 7188. Ответов 45 Метки нет (Все метки) Всем привет! Мне надо организовать двоичный поиск в массиве, но он не отсортирован по возрастанию или убыванию. Вопрос: Как, если это возможно, найти элемент в таком массиве, методом бинарного дерева. 0

@TRam_ зомбяк 1585 / 1219 / 345 Регистрация: 14.05.2017 Сообщений: 3,940
	16.03.2018, 18:18
	lArtl, а синхронизировать изменения у std::vector и std::set как будешь? std::shared_ptr вообще не понятно для чего указал. 0

@TRam_ зомбяк 1585 / 1219 / 345 Регистрация: 14.05.2017 Сообщений: 3,940
	16.03.2018, 20:21
	Хотя... В общем в кое-в-чём ты прав. Так у нас действительно будет автоматически обновляемый указатель при перестроениях и set, и vector. 0