Сложность: 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.
😎 Решение:
func mySqrt(_ x: Int) -> Int {
if x < 2 { return x }
var left = 2
var right = x / 2
while left <= right {
let pivot = left + (right - left) / 2
let num = pivot * pivot
if num > x {
right = pivot - 1
} else if num < x {
left = pivot + 1
} else {
return pivot
}
}
return right
}Ставь 👍 и забирай 📚 Базу знаний