Get this book -> Problems on Array: For Interviews and Competitive Programming
In this article, we have explained the algorithm to Find Cube root using Binary Search along with Time and Space Complexity analysis.
Table of contents:
- Introduction
- Finding cube root using Binary Search
- Perfect Cube
- Cube root with precision
- Time and Space Complexity
Pre-requisites:
Introduction
When someone needs to find the cube of a number, then they can just multiply that number by itself three times, and alas! They have the answer. But, when one needs to go in the other direction (finding cube-root), theirs no direct formula to find this number and, because of this it is required to search this number throughout the space of [1, N].
A little stroll to Linear Search
If you desire, you can skip this and goto the solution
So, I was curious, why not Linear Search? I mean, it's ∛N. maybe a mathematician would know by one look which one is smaller or greater ∛N or log2N
.
Well in my case, I went and took the log
of a bunch of numbers and then compared them together and got the following output.
from math import ceil, log
for i in range(1, 30, 2):
print("{} - {} | {} - {}".format(
i,
ceil(log(i**3, 2)),
i+1,
ceil(log((i+1)**3, 2))
)
)
1 - 0 | 2 - 3 3 - 5 | 4 - 6 5 - 7 | 6 - 8 7 - 9 | 8 - 9 9 - 10 | 10 - 10 11 - 11 | 12 - 11 13 - 12 | 14 - 12 15 - 12 | 16 - 12 17 - 13 | 18 - 13 19 - 13 | 20 - 13 21 - 14 | 22 - 14 23 - 14 | 24 - 14 25 - 14 | 26 - 15 27 - 15 | 28 - 15 29 - 15 | 30 - 15
Conclusion:
As you go further, log starts to become smaller, therefore,
log2N
<∛N
. So, binary search would be better than Linear.
Well, back to the topic...
Finding cube root using Binary Search
Perfect Cube
If we have to find cube root for a perfect cube, then we can just apply binary search directly on the space of [1, N], and return x
where x
equals to x3
.
This should look something like the following,
1 def perfect_cube_root(N):
2 start = 1
3 end = N
4 mid = (start + end) // 2
5
6 while mid != start and mid**3 != N:
7 if mid**3 > N:
8 end = mid
9 else:
10 start = mid
11 mid = (start + end) // 2
12 return mid
The (mid != start) and
condition, in the while loop, help to return a smaller value in case the loop doesn't find a perfect cube root. And without this condition, the loop will run infinitely.
So, for example,
If we do perfect_cube_root(9)
, since 9
comes between two perfect cubes 8
and 27
because of this, the above loop will return 2
, which is a cube-root of 8
.
Why write this function this way?
Well, we're going to use this in the next cube_root
with precision function.
Cube root with precision
Now to find decimal values of a cube root, we can first search for a smaller result using perfect_cube_root(N)
and, if it returns a perfect cube root, then return it or proceed to search for precision.
The idea here is to find a value in decimal which will be a perfect cube root or a nearest smaller value.
In other words, we will search between .0
and .9
, a perfect match or nearest smaller value, and then decrease the power in the case of .0
and .9
, another search will happen in-between .00
and .09
.
And while the above search happens, we should keep adding the found values to the result with increasing precision.
Code for the above idea should look like the following one:
1 def cube_root(N, precision=5):
2 P = lambda a, b: a * 10 ** (-b)
3 result = perfect_cube_root(N)
4 if result**3 == N:
5 return result
6
7 for i in range(1, precision + 1):
8 start = 0
9 end = 9
10 mid = (start + end) // 2
11
12 cube = lambda: (result + P(mid, i))**3
13
14 while start != mid:
15 if cube() > N:
16 end = mid
17 elif cube() < N:
18 start = mid
19 elif cube() == N:
20 return result + P(mid, i)
21
22 mid = (start + end) // 2
23
24 result += P(mid, i)
25
26 return round(result, precision)
Let us look at an example,
If we run cube_root(16.003008)
then it should return 2.52
.
At first, the cube_root
will call perfect_cube_root
, and surely it will get the 2
in return.
Now at line 7
we start for-loop for a range of [1, precision + 1] and initialize start
, end
and mid
as 0, 9 and 4.
Notice, start
, end
, and mid
are not decimals reason for that is just that I did not want to deal with float numbers. Calculating mid
with float values was a mess and, this approach makes it easier to capture a smaller value if it did not find any value, to form a result for perfect cube root.
Anyway, since i = 1
therefore here we're dealing with 10-1
precision, means we're searching for perfect or small in between 2.0
and 2.9
, at this point when loop will take start
and mid
at 5
, start != mid
will break the loop and will proceed for 10-2
.
Hence, it will start searching between 2.50
and 2.59
, in this the loop will find 2.52
as a perfect match and, line 20
will execute, which will add 0.02 ( P(mid, i) )
to result
and return it.
Time and Space Complexity
Time Complexity:
At first, we're performing purely a binary search which should take O(logN) time,
then after this, we perform binary search on space of [0, 9], for P times,
which will total to, Plog(10)
that is, 4P.
therefore,
Time Complexity = O(logN + P)
Space Complexity:
The function itself takes one Number and creates a constant number of variables which use a constant number of space,
therefore,
- Space Complexity = O(1)
With this article at OpenGenus, you must have the complete idea of Finding cube root using Binary Search.