Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.56/34: Рейтинг темы: голосов - 34, средняя оценка - 4.56
61 / 28 / 24
Регистрация: 28.09.2017
Сообщений: 399

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

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

Студворк — интернет-сервис помощи студентам
Всем привет! Мне надо организовать двоичный поиск в массиве, но он не отсортирован по возрастанию или убыванию.
Вопрос: Как, если это возможно, найти элемент в таком массиве, методом бинарного дерева.
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
16.03.2018, 14:25
Ответы с готовыми решениями:

Бинарный поиск с любым видом сортировки
:: Бинарный поиск Помагите сделать бинарный поиск с любым видом сортировки?

Если заменить только один процессор, загрузится ли система без всякой предварительной подготовки?
Конечно знаю правила про перенос системы и подготовки, для перехода на новое железо. Но тем не менее интересно, если тупо заменить только...

Можно ли загрузить модели, текстуры и прочий контент без предварительной их компиляции с помощью ContentPipeline
Можно ли загрузить меши (модели), текстуры и прочий контент без предварительной их компиляции с помощью ContentPipeline? Речь идет,...

45
зомбяк
 Аватар для TRam_
1585 / 1219 / 345
Регистрация: 14.05.2017
Сообщений: 3,940
16.03.2018, 18:18
Студворк — интернет-сервис помощи студентам
lArtl, а синхронизировать изменения у std::vector и std::set как будешь? std::shared_ptr вообще не понятно для чего указал.
0
322 / 174 / 78
Регистрация: 09.10.2014
Сообщений: 809
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).
0
зомбяк
 Аватар для TRam_
1585 / 1219 / 345
Регистрация: 14.05.2017
Сообщений: 3,940
16.03.2018, 20:15
Цитата Сообщение от lArtl Посмотреть сообщение
std::shared_ptr`ом и буду
с std::shared_ptr'ом у тебя будет только гарантия того, что когда объект у тебя удалится только после того, как его сотрёшь/затрёшь новым и в векторе, и в set'е. А синхронизации удаления не будет.
0
322 / 174 / 78
Регистрация: 09.10.2014
Сообщений: 809
16.03.2018, 20:20
Цитата Сообщение от woldemas Посмотреть сообщение
Можно что-нибудь придумать, наверное, какой нибудь связный список из блоков равной длины.
Ага, std::deque.
0
зомбяк
 Аватар для TRam_
1585 / 1219 / 345
Регистрация: 14.05.2017
Сообщений: 3,940
16.03.2018, 20:21
Хотя... В общем в кое-в-чём ты прав. Так у нас действительно будет автоматически обновляемый указатель при перестроениях и set, и vector.
0
322 / 174 / 78
Регистрация: 09.10.2014
Сообщений: 809
16.03.2018, 20:22
Цитата Сообщение от TRam_ Посмотреть сообщение
с std::shared_ptr'ом у тебя будет только гарантия того, что когда объект у тебя удалится только после того, как его сотрёшь/затрёшь новым и в векторе, и в set'е. А синхронизации удаления не будет.
Как и автоматического добавления в std::set при добавлении в std::vector... Все ручками.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
16.03.2018, 20:22

Поиск заданного элемента в упорядоченном массиве(бинарный поиск)
Заполнить одномерный массив из n элементов по формуле приведенной в картинке. Размерность массива задать в виде именованной константы....

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

Поиск заданного элемента в упорядоченном массиве (бинарный поиск)
Заполнить одномерный массив из n элементов согласно таблицы. Размерность массива задать в виде именованной константы. Вывести массив на...

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

Поиск перебором или бинарный поиск в StringGrid
как реализовать поиск в stringgrid (поиск перебором или бинарный поиск)? напр.задаешь в edit.text что искать и stringgrid выводит только...


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

Или воспользуйтесь поиском по форуму:
46
Ответ Создать тему
Новые блоги и статьи
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой. Но использовать несколько программ не удобно. Искал другие. . .
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской) Options Preferences General Language
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент". В данной функции нет апострофов,. . .
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы. Карта этого меню приложена ниже. Нужный пункт выделен красным. Сервис Настройки Поведение
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru