----- Условие ----- Требуется найти корень из числа. Если корень не целое число, то вернуть его целую часть.

----- Решение ----- Можно пройтись в цикле от нуля до первого подходящего числа, но тогда сложность алгоритма по времени составит квадратный корень из x. Есть более быстрое решение.

Используем бинарный поиск (по сути, у нас отсортированный массив от 0 до x). Два указателя каждую итерацию уменьшают количество подходящих чисел в 2 раза. Выходим из цикла, когда указатель на начало станет больше, чем указатель на конец.

Если мы не вышли из функции на строке if (mulRes === x) return midNum, значит, целого решения нет. На последней итерации, когда startNum равен endNum, startNum является ближайшим целым к корню из x. Если x больше, чем квадрат startNum (startNum “слева” от корня из x), то инкрементируем startNum, иначе он уже на нужной позиции (“справа” от корня из x). Возвращаем ближайшее “левое” значение, которое равно startNum - 1.

Сложность данного алгоритма по времени – O(log n), сложность по памяти – O(1).

----- Код ----- /**  * @param {number} x  * @return {number}  */ const mySqrt = function(x) {   if (x === 0) return 0;

let startNum = 0;   let endNum = x;

while (startNum <= endNum) {     const midNum = Math.trunc((endNum + startNum) / 2);

const mulRes = midNum * midNum;

if (mulRes === x) return midNum;

if (x > mulRes) {       startNum = midNum + 1;     } else {       endNum = midNum - 1;     }   }

return startNum - 1; };