← Все вопросы
Что быстрее найдёт элемент: отсортировать и бинпоиск или закинуть в множество?
14
Есть список, и мне нужно много раз проверять «есть ли в нём такой элемент». Что выгоднее: один раз отсортировать список и потом делать бинарный поиск, или закинуть всё в set и проверять через in?
3 ответа
23
Для задачи «просто есть или нет» — множество почти всегда выгоднее.
- set: построение O(n), каждая проверка
x in setв среднем O(1). Для q запросов это O(n + q). - сортировка + бинпоиск: сортировка O(n log n), каждый поиск O(log n). Для q запросов O(n log n + q log n).
set выигрывает и по построению, и по проверке. Бинпоиск по отсортированному массиву имеет смысл, когда тебе дополнительно нужен порядок: найти ближайший элемент, нижнюю/верхнюю границу, элементы в диапазоне (модуль bisect). Если же вопрос строго «членство» — бери set.
Дмитрий Бутырев Если важна ещё и память или нужен порядок — тогда отсортированный массив + bisect. · 4 месяца назад
11
Множество. O(1) на проверку против O(log n), и сортировать ничего не надо.
4
Множество.
Ваш ответ
Войдите, чтобы ответить на вопрос.
