To find the nth root of a number x
, we can use a method called binary search, which efficiently narrows down the possible answer by halving the search range each time.
Understanding Different Cases
Before applying the binary search, we handle a few special cases:
- If x = 0: The result is 0, because 0 raised to any positive power is 0.
- If x = 1: The result is always 1, regardless of the value of n.
- If n = 1: The answer is simply x itself.
- If x is negative and
n
is even: The answer is undefined in real numbers, so we return -1.
- If x is negative and
n
is odd: The result exists and will also be negative.
- If n ≤ 0: The root is undefined or non-standard, so we return -1.
How Binary Search Helps
We know that the nth root of x lies somewhere between 0 and x (or 0 and 1 if x < 1). We set low = 0
and high = max(1, x)
and repeatedly do the following:
- Find the middle point
mid
.
- Raise
mid
to the power n
.
- Compare it with
x
:
- If
midn < x
, we shift our search range to the right (low = mid).
- If
midn > x
, we shift the range to the left (high = mid).
- If it's close enough to
x
(say, within 1e-6
), we consider that our answer.
Why It Works
This approach works well because raising a number to a power is continuous, so the value of midn
increases as mid
increases. By halving the range at each step, we find the accurate root efficiently with a time complexity of O(log x).
This method avoids brute-force checking or floating-point rounding issues and works even for large numbers or high precision.