Код Senior Бинарный поиск обновлено
Бинарный поиск по ответу
Условие
Кучи бананов piles, за час Коко съедает k бананов из одной кучи. Минимальная скорость k, при которой она успеет за h часов.
Примеры
minEatingSpeed([3, 6, 7, 11], 8) // 4
minEatingSpeed([30, 11, 23, 4, 20], 5) // 30
minEatingSpeed([1], 1) // 1
Как подойти
Бинарный поиск не по массиву, а по пространству ответов. Условие применимости - монотонность: подходящие значения образуют непрерывный хвост. Дальше стандартный шаблон левой границы с функцией проверки. Так же решаются «минимальная вместимость корабля», «разделить массив на k частей».
Подсказки: 3
- Ответ лежит в диапазоне от 1 до самой большой кучи.
- Свойство монотонно: если скорость k успевает, то и любая большая успевает.
- Значит ищем левую границу «успевает».
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.