Объясни бинпоиск по ответу
Вопрос
Объясни, что такое бинпоиск по ответу и как ты понимаешь, что задача на него.
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Признак: «найти минимальное или максимальное значение, при котором выполнимо условие»
Есть быстрая проверка выполнимости для заданного ответа
Предикат монотонен, и кандидат это объясняет
Называет границы поиска и шаблон без зацикливания
Сложность: O(проверка · log диапазона)
Что могут спросить следом
- Как выбрать границы?
- Что если ответ дробный?
- Как избежать вечного цикла?
Разбор
Бинпоиск можно вести не по массиву, а по диапазону возможных ответов. Признак: просят минимальную скорость, минимальную вместимость, максимальное расстояние, и при этом для конкретного кандидата легко проверить «получится или нет». Ключ в монотонности: если со скоростью k успеваем, с k + 1 тоже успеем. Тогда ответы делятся на «нельзя» и «можно», и я бинпоиском ищу первое «можно». Беру l как минимально возможный ответ, r как гарантированно достаточный, шаблон с полуинтервалом: если проверка проходит, r = mid, иначе l = mid + 1. Сложность: стоимость проверки, обычно O(n), умножить на log диапазона. Для задачи про бананы это O(n log max). Если ответ дробный, делаю фиксированное число итераций, например 60, вместо условия l < r.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.