Square Root (Integer)

Q: Какова временная сложность бинарного поиска квадратного корня?

Время O(log x) и память O(1) . На каждом шаге диапазон кандидатов делится пополам, поэтому для x = 2^31 - 1 требуется 31 шаг. Перебор начиная с 0 занимает O(√x) шагов — 46340 для того же значения x ; здесь это вполне приемлемо, но при 64-битных входных данных число шагов быстро растёт.

Q: Как метод Ньютона вычисляет целочисленный квадратный корень?

Начните с r = x . Пока r × r > x , заменяйте r на (r + x / r) / 2 , используя целочисленное деление. На каждом шаге r приближается к корню снизу, не пересекая его, а цикл останавливается на целой части квадратного корня. Для x = 2^31 - 1 требуется 19 шагов, и количество верных цифр примерно удваивается на каждом шаге, когда приближение становится достаточно точным.

ЛегкоБинарный поиск Математика и моделирование

+10

Твоя функция получает неотрицательное целое число x и возвращает его целочисленный квадратный корень: наибольшее целое число r, для которого r × r ≤ x. Иными словами, квадратный корень округляется вниз, поэтому для числа, не являющегося полным квадратом, возвращается корень из ближайшего меньшего полного квадрата. Вычисли его самостоятельно, не используя встроенную функцию квадратного корня или возведения в степень.

Функция

mySqrt(x: integer) → integer

xinteger: неотрицательное целое число, квадратный корень из которого нужно извлечь
Возвращаетinteger: квадратный корень из x, округлённый вниз до целого числа

Ограничения

0 ≤ x ≤ 2³¹ - 1
Не вызывай встроенные функции для вычисления квадратного корня, возведения в степень или экспоненты.

Примеры

Ввод: x = 17
Вывод: 4
Пояснение: 4 × 4 = 16 не больше 17, но 5 × 5 = 25 больше, поэтому корень из 17 округляется вниз до 4.

Ввод: x = 49
Вывод: 7
Пояснение: 49 — это полный квадрат: 7 × 7 = 49, поэтому ничего не округляется, и ответ равен точно 7.

+17 скрытых тестов при отправке

Дополнительный вопрос

Как бы ты нашёл целочисленный кубический корень — наибольшее r, для которого r × r × r ≤ x, — если бы x могло быть и отрицательным?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Подсчёт вверх от 0 до тех пор, пока следующий квадрат не превысит x, даёт правильный ответ, но требует по одному шагу на каждую единицу корня — около 46000 шагов в верхней части диапазона. Квадраты 0, 1, 4, 9, 16 и так далее упорядочены, поэтому можно выполнить бинарный поиск последнего кандидата, квадрат которого не превышает x, и уложиться примерно в 31 шаг. В обоих случаях есть подводный камень: переполнение. Квадрат кандидата не всегда помещается в 32 бита.

Считайте вверх от нуля

Идея

Корень — это наибольшее r, для которого r × r ≤ x. Начните с r = 0: его квадрат всегда подходит. Продолжайте увеличивать r на 1, пока квадрат следующего числа тоже подходит. Цикл останавливается на первом r, следующий за которым слишком велик. Это и есть корень. При x = 17 подходят квадраты 1, 4, 9 и 16, а 25 — нет, поэтому цикл останавливается на 4.

Цикл выполняется столько раз, какова величина ответа. Здесь наибольший ответ — 46340, то есть не более 46340 шагов, что выполняется быстро. Однако сложность составляет O(√x), и она растёт вместе с входным значением: обработка 64-битного x может потребовать около 3 × 10^9 шагов.

Обратите внимание на последнюю проверку. При x = 2^31 - 1 цикл возводит 46341 в квадрат, чтобы убедиться, что число слишком велико, а 46341 × 46341 = 2147488281 не помещается в 32-битное целое число. Возводите в квадрат, используя 64 бита.

Алгоритм

Установи root = 0.
Пока (root + 1) × (root + 1) ≤ x, увеличивай root на 1.
Верни root.

def mySqrt(x):
    root = 0
    while (root + 1) * (root + 1) <= x:
        root += 1
    return root

Бинарный поиск по ответу

Идея

Расположи кандидатов 0, 1, 2 и так далее до x и задай каждому один и тот же вопрос: не превышает ли его квадрат x? Ответы будут «да», «да», «да», а затем «нет» для всех кандидатов после корня, потому что квадраты только увеличиваются. Корень — последнее «да». Для этого и предназначен бинарный поиск: когда за последовательностью ответов «да» следуют ответы «нет».

Поддерживай диапазон кандидатов от lo до hi, решение о которых ещё не принято; начни с диапазона от 0 до x. Также заведи переменную best, в которой будет храниться наибольший кандидат, для которого ответ пока был «да». Проверь середину диапазона mid. Если mid × mid ≤ x, корень равен mid или больше него: сохрани mid в best и передвинь lo на mid + 1. Иначе корень меньше: передвинь hi на mid - 1. Когда диапазон опустеет, best и будет корнем.

Проследим за выполнением для x = 17. В диапазоне от 0 до 17 проверяем 8 (64 — слишком много), затем в диапазоне от 0 до 7 проверяем 3 (9 — подходит, best = 3), затем в диапазоне от 4 до 7 проверяем 5 (25 — слишком много), а затем в диапазоне от 4 до 4 проверяем 4 (16 — подходит, best = 4). Диапазон пуст, и ответ — 4. На каждом шаге диапазон сокращается вдвое, поэтому для x = 2^31 - 1 понадобится 31 шаг. Возводи в квадрат, используя 64-битные числа: первое значение mid в этом случае — 1073741823.

Алгоритм

Установи lo = 0, hi = x и best = 0.
Пока lo ≤ hi, вычисляй mid — середину диапазона.
Если mid × mid ≤ x (в 64 битах), присвой best = mid и lo = mid + 1.
Иначе присвой hi = mid - 1.
Верни best.

def mySqrt(x):
    lo, hi = 0, x
    best = 0  # largest candidate seen so far whose square fits
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= x:
            best = mid  # mid fits, so try a larger root
            lo = mid + 1
        else:
            hi = mid - 1  # mid is too big
    return best

Ловушки и крайние случаи

Сам поиск короткий; ошибки скрываются в арифметике и граничных случаях.

Возведение в квадрат с использованием 32 бит. Для x = 2147483647 первый кандидат на середину равен 1073741823, а его квадрат составляет около 1.15 × 10^18. В 32-битном int происходит переполнение, и получается неверное значение, которое может даже показаться достаточно маленьким. Выполняйте умножение с использованием 64 бит или вместо этого сравнивайте m ≤ x / m.
Возведение следующего кандидата в квадрат с использованием 32 бит в цикле подсчёта. Корень из 2^31 - 1 равен 46340, а при последней проверке в цикле возводится в квадрат число 46341, что даёт 2147488281 — больше предела 32-битного числа.
Выход диапазона за пределы 32 бит. Исключительная верхняя граница hi = x + 1 для наибольшего x равна 2147483648, что на единицу больше предела 32-битного числа. При включительной границе hi = x значение lo + hi на первом шаге достигает ровно 2147483647, так что оно помещается без запаса. Используйте 64-битные индексы или lo + (hi - lo) / 2.
Возврат последнего проверенного mid вместо последнего подходящего значения. Для x = 17 поиск завершается после проверки числа 5, которое слишком велико; ответ — сохранённое значение 4.
Нарушение работы с малыми значениями. Поиск, начинающийся с lo = 1, пропускает x = 0, а проверка делением m ≤ x / m приводит к делению на ноль, когда m = 0. Проверьте 0 и 1 отдельно.

Частые вопросы4

Как найти квадратный корень без встроенной функции?

Для целочисленного квадратного корня используйте двоичный поиск. Кандидаты от 0 до x делятся на диапазон, квадраты чисел в котором не превышают x, и диапазон, квадраты чисел в котором больше x; двоичный поиск находит последний кандидат из первого диапазона. Другой распространённый способ — метод Ньютона: он уточняет приближение r с помощью (r + x / r) / 2, пока квадрат не станет подходящим.

Какова временная сложность бинарного поиска квадратного корня?

Время O(log x) и память O(1). На каждом шаге диапазон кандидатов делится пополам, поэтому для x = 2^31 - 1 требуется 31 шаг. Перебор начиная с 0 занимает O(√x) шагов — 46340 для того же значения x; здесь это вполне приемлемо, но при 64-битных входных данных число шагов быстро растёт.

Как метод Ньютона вычисляет целочисленный квадратный корень?

Начните с r = x. Пока r × r > x, заменяйте r на (r + x / r) / 2, используя целочисленное деление. На каждом шаге r приближается к корню снизу, не пересекая его, а цикл останавливается на целой части квадратного корня. Для x = 2^31 - 1 требуется 19 шагов, и количество верных цифр примерно удваивается на каждом шаге, когда приближение становится достаточно точным.

Почему для решения нужны 64-битные целые числа, если ответ помещается в 32 бита?

Ответ не превышает 46340, но проверяемые кандидаты — нет. Бинарный поиск в диапазоне от 0 до x сначала пробует кандидата около 10^9, а его квадрат близок к 10^18, что намного превышает 32-битный предел примерно в 2.1 × 10^9. Возведение в квадрат с использованием 64 бит сохраняет точность сравнения. Сравнение m ≤ x / m позволяет вовсе избежать большого произведения.

Python

def mySqrt(x):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Ввод

x = 17

Ожидается