Сложность: easy
Дано неотрицательное целое число x. Верните квадратный корень из x, округлённый вниз до ближайшего целого числа. Возвращаемое целое число также должно быть неотрицательным.
Вы не должны использовать встроенные функции или операторы для возведения в степень.
Например, не следует использовать pow(x, 0.5) в C++ или x ** 0.5 в Python.
Пример:
Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.
👨💻 Алгоритм:
1️⃣Если x < 2, верните x. Установите левую границу left = 2 и правую границу right = x / 2.
2️⃣Пока left ≤ right:
Возьмите num = (left + right) / 2 в качестве предположения. Вычислите num × num и сравните его с x:
Если num × num > x, переместите правую границу right = pivot − 1.
В противном случае, если num × num < x, переместите левую границу left = pivot + 1.
В противном случае num × num == x, целочисленный квадратный корень найден, давайте вернем его.
3️⃣Верните right.
😎 Решение:
class Solution:
def mySqrt(self, x: int) -> int:
if x < 2:
return x
left, right = 2, x // 2
while left <= right:
pivot = left + (right - left) // 2
num = pivot * pivot
if num > x:
right = pivot - 1
elif num < x:
left = pivot + 1
else:
return pivot
return right
Ставь 👍 и забирай 📚 Базу знаний