Почему это работает
- Квадраты растут: 1, 4, 9, 16, 25, … Поэтому проверки «k · k <= x» идут «да, да, …, нет, нет», а ответ — последнее «да». Бинарный поиск находит эту границу.
- Если mid подходит, он может быть ответом, и lo = mid его оставляет. Если нет, не подходит и ничего больше него: hi = mid − 1.
- Раз lo = mid может оставить lo на месте, mid округляем вверх: когда кандидатов два, он попадает на верхний, и диапазон всегда сужается.
Сложность
Время O(log x): диапазон 1..x / 2 на каждом шаге делится пополам. Память O(1). При большом x произведение mid · mid не влезает в 32-битное целое: сравнивайте mid с x / mid или считайте в 64 битах.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗