Выбор ответа Middle Бинарный поиск обновлено
Целый корень
Вопрос
Найти floor(sqrt(n)) без Math.sqrt для n до 2³¹. Какой подход и сложность?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Бинпоиск по ответу: последний m, где m·m ≤ n, O(log n). Предикат m m <= n истинен до ответа и ложен после: ищем последнюю истину.
Варианты ответа
- Перебор m от 1, пока m·m ≤ n, это оптимально: O(√n)
- Перебор m до n/2 с проверкой m·m ≤ n: O(n)
- Бинпоиск по ответу: последний m, где m·m ≤ n, O(log n)правильный ответ
- Сортировка квадратов чисел до n и бинпоиск по ним
Разбор
Предикат m * m <= n истинен до ответа и ложен после: ищем последнюю истину. O(log n). Квадрат большого mid может выйти за 2⁵³ и потерять точность, но такие квадраты намного больше n, и сравнение не ошибается; совсем надёжно сравнивать m <= n / m.
- Перебор корректен, но O(√n): для n около 2³¹ это 46 тысяч шагов против 31.
- Перебор до n/2 O(n).
- Сортировка не к месту.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.