Помоготе разобратся с бинарным поиском квадратного корня

Вопрос-ответ JavaScript
2

Решение в лоб - это взять готовый алгоритм, если есть на JS, или взять на другом языке (если нет готового на JS) и переделать на JS:

function findSqrt(x)
{
    // базовый вариант
    if (x < 2) {
        return x;
    }
 
    // для хранения пола `sqrt(x)`
    let result;
 
    // квадратный корень из `x` не может быть больше, чем `x/2` для `x > 1`
    let start = 1;
    let end = Math.floor(x / 2);
 
    while (start <= end) {
        // найти средний элемент
        const mid = Math.floor((start + end) / 2);
        const sqr = mid * mid;
 
        // вернуть `mid`, если `x` - правильный квадрат
        if (sqr == x) {
            return mid;
        }
 
        // если `mid×mid` меньше, чем `x`
        else if (sqr < x)
        {
            // отбрасываем левое пространство поиска
            start = mid + 1;
 
            // обновляем результат, так как нам нужен пол
            result = mid;
        }
 
        // если `mid×mid` больше, чем `x`
        else {
            // отбрасываем правильное пространство поиска
            end = mid - 1;
        }
    }
 
    // возвращаем результат
    return result;
}
 
for (let i = 0; i <= 16; i++) {
    console.log(`sqrt${i} = ${findSqrt(i)}`);
}

Результат:

sqrt(0) = 0
sqrt(1) = 1
sqrt(2) = 1
sqrt(3) = 1
sqrt(4) = 2
sqrt(5) = 2
sqrt(6) = 2
sqrt(7) = 2
sqrt(8) = 2
sqrt(9) = 3
sqrt(10) = 3
sqrt(11) = 3
sqrt(12) = 3
sqrt(13) = 3
sqrt(14) = 3
sqrt(15) = 3
sqrt(16) = 4

Источник: Найдите квадратный корень числа с помощью двоичного поиска

1 лайк