Условие:
Написать функцию на Python, которая получает целое числоx и выдает округленное вниз до ближайшего целого значение квадратного корня от x. Сложность O(log x)
1. Бинарный поиск:
- Начинаем с диапазона от 0 до x.
- В каждой итерации вычисляем середину ( mid ), проверяем mid 2 и сравниваем с x.
- Если mid2=x, то нашли точный квадратный корень и возвращаем mid.
- Если mid 2<x, то ищем в правой половине диапазона.
- Если mid 2>x, то ищем в левой половине.
2. По завершении бинарного поиска переменная right будет хранить наибольшее число, для которого right 2 ≤ x, что и будет искомым округленным вниз квадратным корнем.
Решение:
Давайте напишем функцию на Python, которая будет находить округленный вниз до ближайшего целого квадратный корень из целого числа x с использованием бинарного поиска. Мы будем следовать описанным вами шагам.
Шаг 1: Определение функции
Мы начнем с определения функции, которая принимает целое число x.
Шаг 2: Инициализация переменных
Инициализируем переменные
left и right, которые будут представлять границы нашего поиска. left будет равен 0, а right будет равен x.Шаг 3: Бинарный поиск
В цикле будем вычислять середину
mid и проверять, является ли квадрат mid равным, меньше или больше x. В зависимости от этого будем корректировать границы поиска.Шаг 4: Возврат результата
По завершении поиска вернем значение
right, которое будет округленным вниз квадратным корнем из x.Код функции
Вот как будет выглядеть код:
1. : Если x отрицательное, выбрасываем исключение, так как квадратный корень из отрицательного числа не определен. 2. : устанавливается в 0, а в x. 3. : - Вычисляем как среднее значение между и . - Сравниваем квадрат с x: - Если равны, возвращаем . - Если меньше, сдвигаем вправо. - Если больше, сдвигаем влево. 4. : После завершения цикла возвращаем , который будет округленным вниз квадратным корнем из x. Таким образом, мы реализовали функцию, которая находит округленный вниз квадратный корень с использованием бинарного поиска за O(log x).
