Mediumbisect
Что такое bisect?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
bisect — бинарный поиск и вставка в отсортированный list. Поиск O(log n), вставка O(n) из-за shift.
import bisect
a = [1, 3, 3, 5, 7]
# Поиск позиции вставки
bisect.bisect_left(a, 3) # 1 (перед первым 3)
bisect.bisect_right(a, 3) # 3 (после последнего 3)
# Вставка с сохранением порядка
bisect.insort(a, 4) # [1, 3, 3, 4, 5, 7]
# Discretization — выбор интервала из boundaries
age_groups = [0, 18, 65]
idx = bisect.bisect_right(age_groups, 25) # 2 → 'adult'bisect_left— позиция перед равными;bisect_right— после;- List должен быть отсортирован, иначе UB;
- Аналог
std::lower_boundв C++; - Для частой вставки в middle лучше
sortedcontainers(3rd party).
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.