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