Найдите N-й корень числа, используя метод деления пополам

Даны два положительных целых числа N и P . Задача состоит в том, чтобы найти N -й корень P .

Примеры:

Input: P = 1234321, N = 2
Output: 1111
Explanation: square root of 1234321 is 1111.

Input: P = 123456785, N = 20
Output: 2.53849

Подход: Существуют различные способы решения данной проблемы. Здесь приведенный ниже алгоритм основан на математической концепции, называемой методом деления пополам для поиска корней. Чтобы найти корень N -й степени заданного числа P, мы составим уравнение, сформированное в x как ( x ^p - P = 0 ), и цель состоит в том, чтобы найти положительный корень этого уравнения, используя метод деления пополам.

Как работает метод деления пополам?
Возьмем интервал (a, b) такой, что уже известно, что корень существует в этом интервале. После этого найдите середину интервала и осмотрите значение функции и ее производная при x = mid.

• Если значение функции равно 0, это означает, что корень найден
• Если значение функции положительно, а ее производная отрицательна, значит, корень лежит в правой половине.
• Если значение функции положительно и ее производная положительна, то корень лежит в левой половине.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (log P).
Вспомогательное пространство: O(1).