Sqrt(x)

Лёгкая№69поиск по ответу

Дано неотрицательное целое x. Нужно вернуть квадратный корень из него, округлённый вниз, не пользуясь встроенными степенью и корнем. Наш пример: x = 20 — ответ 4: 4 · 4 = 16 не больше 20, а 5 · 5 = 25 уже больше.

69 Sqrt(x)Разбор · 1×

Пример: x = 20. Клетки — кандидаты в корни 1..10; ищем наибольшее k, у которого k · k <= 20.

кандидаты в корень k12345678910mid · mid—
корень ещё возможенсередина, проверяемотброшенокорень

20 не меньше 2: ищем

01/21
сначала · назад · пуск · шаг
Скорость
1function mySqrt(x):
2 if x < 2:
3 return x
4 lo = 1
5 hi = floor(x / 2) // the root is at most x / 2
6 while lo < hi:
7 mid = ceil((lo + hi) / 2) // round up
8 if mid * mid <= x:
9 lo = mid // mid fits: keep it
10 else:
11 hi = mid - 1
12 return lo
состояние
x
20
lo
–
hi
–
mid
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Квадраты растут: 1, 4, 9, 16, 25, … Поэтому проверки «k · k <= x» идут «да, да, …, нет, нет», а ответ — последнее «да». Бинарный поиск находит эту границу.
  2. Если mid подходит, он может быть ответом, и lo = mid его оставляет. Если нет, не подходит и ничего больше него: hi = mid − 1.
  3. Раз lo = mid может оставить lo на месте, mid округляем вверх: когда кандидатов два, он попадает на верхний, и диапазон всегда сужается.

Сложность

Время O(log x): диапазон 1..x / 2 на каждом шаге делится пополам. Память O(1). При большом x произведение mid · mid не влезает в 32-битное целое: сравнивайте mid с x / mid или считайте в 64 битах.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.