Задача: 69. Sqrt(x)
Сложность: 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.

😎 Решение:

var mySqrt = function (x) {
    if (x < 2) return x;
    let num;
    let pivot,
        left = 2,
        right = Math.floor(x / 2);
    while (left <= right) {
        pivot = left + Math.floor((right - left) / 2);
        num = pivot * pivot;
        if (num > x) right = pivot - 1;
        else if (num < x) left = pivot + 1;
        else return pivot;
    }
    return right;
};

Ставь 👍 и забирай 📚 Базу знаний