Алгоритми та структури даних · Middle · Запитання 15 з 75
Що означає «бінарний пошук по відповіді»?
- 1Бінарний пошук у масиві відповідей від користувачів
- 2Перевірка кожної можливої відповіді від 1 до n, доки одна не підійде
- ✓Правильна відповідь: Пошук найменшого значення, що проходить монотонну перевірку
Пояснення
Якщо «чи можна впоратися з x?» хибне до певного моменту й істинне після нього, x можна шукати бінарним пошуком. Приклад: мінімальна вантажопідйомність корабля, щоб доставити посилки за D днів, де кожна перевірка - жадібний прохід за O(n).