Решение

Ответ:

Для x >= 2 квадратный корень всегда меньше x/2 и больше нуля: 0 < a < x/2. Так как a это число, проблема сводится к итерации по отсортированному набору целых чисел. Здесь на сцену выходит бинарный поиск.

Алгоритм (left — левая граница, right — правая):

Если x < 2, вернуть x.

Установить левую границу на 2, а правую границу на x/2.

Цикл, пока left <= right:

  Берем num = (left + right) / 2 в качестве предположения.

  Вычисляем num * num и сравниваем его с x:

  Если num * num > x, перемещаем правую границу вправо = pivot - 1

  В противном случае, если num * num < x, перемещаем левую границу влево = pivot + 1.

  Если num * num == x, здесь целочисленный квадратный корень, возвращаем его

Возвращаем right