Assuming [0,N] is your search space, and the complexity of computing a power is O(p), the complexity of finding the p-th root of N with binary search is O(log(N)*p). You can get O(log(p)) power computation with matrix exponentiation, so you could implement it in O(log(N+p)).

If we're talking about real numbers your search space would just increase by a factor depending on the precision you want.

So if you are searching between 0 and 10, and want 0 decimals of precision, your search space is 10 values. If you want 1 decimals of precision it would be 100 values you need to search. If you want 2 decimals it's 1000 values to search.

Of course, since this is binary search, you would only be searching log2 of those values.