Сложность: 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 {
public int mySqrt(int x) {
if (x < 2) return x;
long num;
int pivot, left = 2, right = x / 2;
while (left <= right) {
pivot = left + (right - left) / 2;
num = (long) pivot * pivot;
if (num > x) right = pivot - 1;
else if (num < x) left = pivot + 1;
else return pivot;
}
return right;
}
}Ставь 👍 и забирай 📚 Базу знаний